Optimization Online


A Branch & Bound Algorithm for Robust Binary Optimization with Budget Uncertainty

Christina Büsing(buesing***at***math2.rwth-aachen.de)
Timo Gersing(gersing***at***math2.rwth-aachen.de)
Arie M.C.A. Koster(koster***at***math2.rwth-aachen.de)

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 & 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.

Keywords: Robust Optimization, Combinatorial Optimization, Mathematical Programming, Branch and Bound, Computation

Category 1: Integer Programming (0-1 Programming )

Category 2: Robust Optimization

Category 3: Combinatorial Optimization (Branch and Cut Algorithms )


Download: [PDF]

Entry Submitted: 10/21/2021
Entry Accepted: 10/21/2021
Entry Last Modified: 10/21/2021

Modify/Update this entry

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Optimization Society