ROMAE: Robust Optimization Models and Algorithms with Explorable Uncertainty

ROMAE：具有可探索不确定性的鲁棒优化模型和算法

• 批准号: 534441421
• 负责人: Dr. Michael Hartisch
• 金额: --
• 依托单位: Université Montpellier Montpellier
• 依托单位国家: 德国
• 项目类别: Research Grants
• 资助国家: 德国
• 项目状态: 未结题
• 来源: https://gepris.dfg.de/gepris/projekt/534441421?language=en
• 关键词: ROMAE; Robust; Optimization; Models; Algorithms

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.

处理决策问题中的不确定性对于找到在实践中有用的解决方案至关重要。随着鲁棒优化的概念，一个强大的工具箱已经开发出来，以确定解决方案，对冲一组给定的场景。然而，这种范式的大多数变体缺乏的是探索不确定性的可能性，也就是说，在做出决定之前，要求额外的查询以获得对环境的更好的理解。在可探索不确定性的名称下，对这类概念进行了分析。一种这样的方法可以是在具有最小必要数量的查询的环境的真实表现中找到可证明的最优解决方案。通常，这样的问题被处理类似于在线优化问题。这意味着我们将我们需要的查询数量与一个对环境有充分了解的无所不知的玩家所需的最佳查询数量进行比较。我们考虑的所有情况下的最坏情况比率给出了竞争力值。在这个项目中，我们建议通过一种完全不同的方法来分析可探索的不确定性问题。我们不与想象中的无所不知的玩家进行比较，而是考虑只使用实际可见的信息的最佳策略。为此，我们将不确定性探索问题表述为多阶段鲁棒优化问题，其中阶段数量可能很大。这创造了使用比以前可能的全新解决方案策略的机会。我们利用量化整数规划找到最优解，开发新的启发式求解程序，我们可以分析这些问题的逼近性，从而更紧密的界限和更好地理解问题。此外，我们扩展了可探索的不确定性分布鲁棒问题的概念。借鉴随机优化领域，这里的基本思想是构建一个可能的概率分布的模糊集。在经典设置中，我们希望找到一个决策，这样我们就可以防止来自模糊集的最坏情况分布。通过在这种情况下使用可探索的不确定性，我们包括在做出决定之前测量分布参数的可能性，这会导致更明智的解决方案。随着我们开创的新模型和算法，处理决策中不确定性的新方法变得可用。