HIRO – Hard Instances and Improved Algorithms for Robust Combinatorial Optimization

• Applicant: Professor Dr. Marc Goerigk
• Subject Area: Accounting and Finance ; Theoretical Computer Science
• Term: from 2020 to 2022
• Project identifier: Deutsche Forschungsgemeinschaft (DFG) - Project number 431609588

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.

• DFG Programme: Research Grants