Network Flow Models for Robust Binary Optimization with Selective Adaptability

Adaptive robust optimization problems have received significant attention in recent years but remain notoriously difficult to solve when recourse decisions are discrete. In this paper, we propose new reformulation techniques for adaptive robust binary optimization (ARBO) problems with objective uncertainty. Without loss of generality, we focus on ARBO problems with “selective adaptability,” a term we coin to describe a common class of linking constraints between first-stage and second-stage solutions. Our main contributions involve reformulating and approximating these ARBO problems as network flow models by leveraging ideas from the decision diagram literature. We show that these models are versatile and easy to customize and can generate feasible solutions, primal bounds, and dual bounds. Furthermore, in contrast to existing approaches, they require no specialized algorithms and can be solved directly using standard optimization solvers. Through an extensive set of computational experiments, we show that our models generate high-quality solutions and dual bounds in significantly less time than popular benchmark methods. History: Accepted by Andrea Lodi/Design & Analysis of Algorithms-Discrete. Supplemental Material: The software that supports the findings of this study is available within the paper and its Supplemental Information ( https://pubsonline.informs.org/doi/suppl/10.1287/ijoc.2024.0718 ) as well as from the IJOC GitHub software repository ( https://github.com/INFORMSJoC/2024.0718 ). The complete IJOC Software and Data Repository is available at https://informsjoc.github.io/ .