Optimization under Explorable Uncertainty

可探索的不确定性下的优化

• 批准号: 517912373
• 负责人: Professorin Dr. Nicole Megow
• 金额: --
• 依托单位: Arbeitsgruppe Kombinatorische Optimierung und Logistik
• 依托单位国家: 德国
• 项目类别: Research Grants
• 资助国家: 德国
• 项目状态: 未结题
• 来源: https://gepris.dfg.de/gepris/projekt/517912373?language=en
• 关键词: Optimization; under; Explorable; Uncertainty

Uncertainty in the input data or even lack of information are an omnipresent issue in real-life decision making. The framework of optimization under explorable uncertainty deals with problems where part of the input data is uncertain but can be obtained by a query operation at a certain cost. Challenging questions are: Which input elements shall be queried? How much information is required to achieve a certain solution quality? The goal of this project is to develop new techniques for balancing the cost for data exploration and the benefit for the solution quality. Our focus lies on designing algorithms with mathematical guarantees on the quality of obtained solutions. We advance the state of the art by quantifying the power and limits of parallel decision-making and by studying new models beyond the classical worst-case considerations. We envision a unified methodology for coping with (stochastic) explorable uncertainty. We investigate also recent models such as learning-augmented algorithms taking error-prone predictions into account.

在现实生活中，输入数据的不确定性甚至信息的缺乏是一个无处不在的问题。可探索不确定性下的优化框架处理部分输入数据是不确定的，但可以通过查询操作以一定的代价获得的问题。具有挑战性的问题是：应该查询哪些输入元素？需要多少信息才能达到特定的解决方案质量？该项目的目标是开发新的技术，以平衡数据探索的成本和解决方案质量的收益。我们的重点在于设计对所获得解的质量具有数学保证的算法。我们通过量化并行决策的力量和限制，并通过研究超越经典最坏情况考虑的新模型，推动了最新技术的发展。我们设想了一种处理(随机)可探索不确定性的统一方法。我们还研究了最近的模型，例如考虑到容易出错的预测的学习增强算法。