ROMAE: Robust Optimization Models and Algorithms with Explorable Uncertainty

点击翻译按钮获取中文摘要

Handling uncertainty in decision making problems is crucial to find solutions that are useful in practice. With the concept of robust optimization, a powerful toolbox has been developed to identify solutions that hedge against a given set of scenarios. What most variants of this paradigm lack, however, is the possibility to explore the uncertainty, that is, to ask additional queries to gain an improved understanding of the environment before making a decision. Under the name of explorable uncertainty, some concepts of this kind have been analyzed. One such approach may be to find a provably optimal solution in the true manifestation of the environment with the smallest necessary number of queries. Usually, such problems are treated similar to online optimization problems. This means that we compare the number of queries that we need with the best possible number of queries that is required by an omniscient player who has full knowledge of the environment. The worst-case ratio over all instances that we consider gives a competitiveness value. In this project, we propose to analyze problems in explorable uncertainty through a completely different approach. Instead of comparing with an imaginary omniscient player, we consider the best possible strategy that uses only the information that is actually visible. To this end, we formulate problems with uncertainty exploration as multi-stage robust optimization problems, where the number of stages is potentially large. This creates opportunities to use completely new solution strategies than previously possible. We make use of quantified integer programming to find optimal solutions, develop new heuristic solution procedures and we can analyze the approximability of such problems, which results in tighter bounds and better understanding of problems. Additionally, we extend the notion of explorable uncertainty to distributionally robust problems. Drawing from the field of stochastic optimization, the underlying idea here is to construct an ambiguity set of possible probability distributions. In the classic setting, we would like to find a decision, such that we protect against the worst-case distribution from the ambiguity set. By using explorable uncertainty in this setting, we include the possibilities to measure parameters of the distribution before making a decision, which results in better-informed solutions. With the new models and algorithms that we pioneer, novel ways to handle uncertainty in decision making become available.