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.