Almost Robust Optimization with Binary Variables

The main goal of this paper is to develop a simple and tractable methodology (both theoretical and computational) for incorporating data uncertainty into optimization problems in general and into discrete (binary decision variables) optimization problems in particular. We present the Almost Robust Optimization (ARO) model that addresses data uncertainty for discrete optimization models. The ARO model trade-offs the objective function value with robustness, to find optimal solutions that are almost robust (feasible under most realizations). The proposed model is attractive due to its simple structure, its ability to model dependence among uncertain parameters, and its ability to incorporate the decision maker’s attitude towards risk by controlling the degree of conservatism of the optimal solution. Specifically, we define the Robustness Index that enables the decision maker to adjust the ARO to better suit her risk preference. We also demonstrate the potential advantages of being almost robust as opposed to being fully robust. To solve the ARO model with discrete decision variables efficiently, we develop a decomposition approach that decomposes the model into a deterministic master problem and a single subproblem that checks the master problem solution under different realizations and generates cuts if needed. Computational experiments demonstrate that the decomposition approach is able to find the optimal solutions up to three orders-of-magnitude faster than the original formulation. We demonstrate our methodology on the knapsack problem with uncertain weights, the capacitated facility location problem with uncertain demands, and the vehicle routing problem with uncertain demands and travel times