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

• Final Report Year: 2023

Final Report Abstract

To solve decision making problems, powerful and standardized algorithmic toolboxes have become available. In particular in mixed-integer linear programming, there is a productive cycle between the community-based development of new and challenging problems, solution methods, and their implementation in commercial and academic software. Such a success is only possible if the abstract shape of problems under consideration is well-defined. At the same time, this standardization is largely missing for decision making problems under uncertainty. Besides the structure of the set of feasible solutions, we also need to choose one of many available decision criteria and types of uncertainty sets. This contributes to a much more fractured landscape of benchmarking problems, algorithms and software. In this project, we focussed on robust combinatorial optimization problems, which often belong to the class of hard problems. To put the field on a safer experimental footing, we studied different methods to construct hard instances. A widespread standard is to choose parameter values from a uniform distribution. Using a wider range of sampling methods, we have been able to derive instances that are harder to solve by several orders of magnitude. Which sampling method to choose depends on the decision criterion and, of course, the type of uncertainty. In most cases, these instances can be further made more challenging by running an optimization model to design problem parameters. Connected to the generation of instances is the problem of reducing instances to keep the essential problem information intact. For example, if one scenario is dominated by another scenario, it can be removed from the problem. We studied this scenario aggregation problem through the lens of a disciplined optimization problem that gives an approximation guarantee on the quality of aggregation. It is thus leading to a heuristic that performs well in practice. We further made use of data-driven machine learning methods to model uncertainty sets that fit historic data well, and to learn effective algorithms based on a set of problem instances that were previously solved. We extended the current knowledge of problem complexity by studying new types of uncertainty sets and dynamic decision making problems with more than one stage.

Publications

• On the recoverable robust traveling salesman problem. Optimization Letters, 10(7), 1479-1492.
  Chassein, André & Goerigk, Marc
  
• Robust Combinatorial Optimization with Locally Budgeted Uncertainty. Open Journal of Mathematical Optimization, 2, 1-18.
  Goerigk, Marc & Lendl, Stefan
  
• Robust two-stage combinatorial optimization problems under convex second-stage cost uncertainty. Journal of Combinatorial Optimization, 43(3), 497-527.
  Goerigk, Marc; Kasperski, Adam & Zieliński, Paweł
  
• Data-driven robust optimization using deep neural networks. Computers & Operations Research, 151, 106087.
  Goerigk, Marc & Kurtz, Jannis
  
• Optimal scenario reduction for one- and two-stage robust optimization with discrete uncertainty in the objective. European Journal of Operational Research, 310(2), 529-551.
  Goerigk, Marc & Khosravi, Mohammad
  
• Benchmarking problems for robust discrete optimization. Computers & Operations Research, 166, 106608.
  Goerigk, Marc & Khosravi, Mohammad
  
• On the complexity of robust multi-stage problems with discrete recourse. Discrete Applied Mathematics, 343, 355-370.
  Goerigk, Marc; Lendl, Stefan & Wulf, Lasse
  
• Data-driven prediction of relevant scenarios for robust combinatorial optimization. Computers & Operations Research, 174, 106886.
  Goerigk, Marc & Kurtz, Jannis