HIRO – Hard Instances and Improved Algorithms for Robust Combinatorial Optimization

HIRO â 鲁棒组合优化的硬实例和改进算法

• 批准号: 431609588
• 负责人: Professor Dr. Marc Goerigk
• 金额: --
• 依托单位: Lehrstuhl Business Decisions and Data Science
• 依托单位国家: 德国
• 项目类别: Research Grants
• 财政年份: 2020
• 资助国家: 德国
• 起止时间: 2019-12-31 至 2021-12-31
• 项目状态: 已结题
• 来源: https://gepris.dfg.de/gepris/projekt/431609588?language=en
• 关键词: HIRO; Hard; Instances; Improved; Algorithms

Nearly every decision problem is affected by uncertainty: How should I plan, when I don’t know the future? A recent method to handle such problems is robust optimisation. Given a set of possible outcomes, a robust solution is one that performs better than any other solution under the worst-case outcome. While this may seem too conservative, the degree of robustness can be controlled through the size of the set of possible outcomes.While the robust optimisation method has been shown to perform well for many real-world applications from inventory control over airline scheduling to emergency logistics, it turns out that most robust combinatorial optimisation problems (i.e., decisions where all variables are either 0 or 1) belong to the class of hard problems, which cannot be solved efficiently. Many algorithms have been developed for these challenging problems. But comparing them is difficult, as there is no benchmark set of problems available that every researcher could use. Also, previous algorithms are usually not made available, and so have to be re-implemented.In the best case, experimental and theoretical research feed into each other: What we learn from experiments gives new insight into complexity analysis and leads to the development of improved solution methods. The difficult situation in robust combinatorial optimisation regarding experiments blocks this so-called algorithm engineering cycle. Accordingly, many hardness results remain superficial and don’t reflect the computational complexity (or lack thereof) that we can observe. The lack of benchmark problems means that solution methods have not seen as much improvement as one would expect from the size of community working on robust optimisation.The vision of this research project is to unblock this cycle, paving the way for successful and efficient further research in robust combinatorial optimisation. We create a benchmark set of problem instances, using both artificial (hard) and real-world problem data. The benchmark set will be made available by publishing it through a dedicated website. Based on these problem instances, we then refine the complexity analysis and develop new and efficient solution algorithms. Our methods are implemented as part of a code library, which is also made available online.The applicant and the Mercator Fellow have a strong background in all of the above problem aspects. By following the development cycle twice, we will have created a new toolbox of code, complexity analysis, algorithms, and benchmark instances that allow for a completely new perspective on the field, thus putting it on a strong footing for the future.

几乎每一个决策问题都受到不确定性的影响：当我不知道未来时，我应该如何计划？最近的一种处理此类问题的方法是鲁棒优化。给定一组可能的结果，健壮的解决方案是在最坏情况下比任何其他解决方案都表现得更好的解决方案。虽然这似乎过于保守，但鲁棒性的程度可以通过可能结果集的大小来控制。虽然鲁棒优化方法已被证明在许多现实世界的应用中表现良好，从航空公司调度的库存控制到紧急物流，但事实证明，大多数鲁棒组合优化问题（即，所有变量为0或1的决策）属于难问题类，不能有效地解决。许多算法已经开发了这些具有挑战性的问题。但是比较它们是困难的，因为没有每个研究人员都可以使用的基准问题集。在最好的情况下，实验和理论研究相互补充：我们从实验中学到的东西为复杂性分析提供了新的见解，并导致改进的解决方案的发展。关于实验的鲁棒组合优化的困难情况阻碍了这个所谓的算法工程周期。因此，许多硬度结果仍然是肤浅的，并没有反映我们可以观察到的计算复杂性（或缺乏计算复杂性）。基准问题的缺乏意味着解决方案的方法并没有看到尽可能多的改进，因为人们会期望从社区的规模工作在强大的optimization.The研究项目的愿景是解开这个循环，铺平了道路，为成功和有效的进一步研究在强大的组合优化。我们使用人工（硬）和真实世界的问题数据创建一组基准问题实例。这套基准将通过一个专门网站公布。基于这些问题的实例，我们然后细化的复杂性分析和开发新的和有效的解决方案的算法。我们的方法是作为代码库的一部分实现的，该代码库也可以在线获得。申请人和墨卡托研究员在上述所有问题方面都有很强的背景。通过遵循两次开发周期，我们将创建一个新的代码工具箱，复杂性分析，算法和基准测试实例，允许对该领域进行全新的视角，从而为未来奠定坚实的基础。