A branch and bound algorithm for robust binary optimization with budget uncertainty

Mathematical Programming Computation, vol. 15, pp. 269–326

Abstract

Abstract Since its introduction in the early 2000s, robust optimization with budget uncertainty has received a lot of attention. This is due to the intuitive construction of the uncertainty sets and the existence of a compact robust reformulation for (mixed-integer) linear programs. However, despite its compactness, the reformulation performs poorly when solving robust integer problems due to its weak linear relaxation. To overcome the problems arising from the weak formulation, we propose a bilinear formulation for robust binary programming, which is as strong as theoretically possible. From this bilinear formulation, we derive strong linear formulations as well as structural properties for robust binary optimization problems, which we use within a tailored branch and bound algorithm. We test our algorithm’s performance together with other approaches from the literature on a diverse set of “robustified” real-world instances from the MIPLIB 2017. Our computational study, which is the first to compare many sophisticated approaches on a broad set of instances, shows that our algorithm outperforms existing approaches by far. Furthermore, we show that the fundamental structural properties proven in this paper can be used to substantially improve the approaches from the literature. This highlights the relevance of our findings, not only for the tested algorithms, but also for future research on robust optimization. To encourage the use of our algorithms for solving robust optimization problems and our instances for benchmarking, we make all materials freely available online.

Authors 3

1. Christina Büsing Aachen Combinatorial Optimization

   RWTH Aachen University

   Affiliation as printed

   Combinatorial Optimization, RWTH Aachen University, Ahornstraße 55, 52074, Aachen, Germany

2. Timo Gersing corresponding Aachen Combinatorial Optimization

   RWTH Aachen University

   Affiliation as printed

   Combinatorial Optimization, RWTH Aachen University, Ahornstraße 55, 52074, Aachen, Germany

3. Arie M. C. A. Koster Aachen Discrete Optimization

   RWTH Aachen University

   Affiliation as printed

   Discrete Optimization, RWTH Aachen University, Pontdriesch 10-12, 52062, Aachen, Germany