HIRO – Hard Instances and Improved Algorithms for Robust Combinatorial Optimization

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

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.