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.