Network Flow Models for Robust Binary Optimization with Selective Adaptability

doi:10.1287/ijoc.2024.0718

Network Flow Models for Robust Binary Optimization with Selective Adaptability

2026-01-01

0

PRE

AI

DOI：10.1287/ijoc.2024.0718

Original

Original request for help

Save

Abstract

En 中文

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.

Keywords:

decision diagrams

discrete optimization

network flow models

robust optimization

Network Flow Models for Robust Binary Optimization with Selective Adaptability

Abstract

Journal

Organization