Almost Robust Discrete Optimization

The main goal of this paper is to present a simple and tractable methodology for incorporating data uncertainty into optimization models in the presence of binary variables. We introduce the Almost Robust Discrete Optimization (ARDO). ARDO extends the Integrated Chance-Constrained approach, developed for linear programs, to include binary integer variables. Both models trade off the objective function value with robustness and find optimal solutions that are almost robust (feasible under most realizations). These models are attractive due to their simplicity, ability to capture dependency among uncertain parameters, and that they incorporate the decision maker’s attitude towards risk by controlling the degree of conservatism of the optimal solution. To solve the ARDO model efficiently, we decompose it into a deterministic master problem and a single subproblem that checks the master problem solution under different realizations and generates cuts if needed. In contrast to other robust optimization models that are less tractable with binary decision variables, we demonstrate that with these cuts, the ARDO remains tractable. Computational experiments for the capacitated single-source facility location problem where demands in each node are uncertain demonstrate the effectiveness of our approach.