  


On the Power of Robust Solutions in TwoStage Stochastic and Adaptive Optimization Problems
Dimitris Bertsimas(dbertsimmit.edu) Abstract: We consider a twostage mixed integer stochastic optimization problem and show that a static robust solution is a good approximation to the fullyadaptable twostage solution for the stochastic problem under fairly general assumptions on the uncertainty set and the probability distribution. In particular, we show that if the right hand side of the constraints is uncertain and belongs to a {\em symmetric} uncertainty set (such as hypercube, ellipsoid or normball) and the probability measure is also {\em symmetric}, then the cost of the optimal fixed solution to the corresponding robust problem is at most twice the optimal expected cost of the twostage stochastic problem. Furthermore, we show that the bound is tight for symmetric uncertainty sets and can be arbitrarily large if the uncertainty set is not symmetric. We refer to the ratio of the optimal cost of the robust problem and the optimal cost of the twostage stochastic problem as the {\em stochasticity gap}. We also extend the bound on the stochasticity gap for another class of uncertainty sets referred to as {\em positive}. If both the objective coefficients and right hand side are uncertain, we show that the stochasticity gap can be arbitrarily large even if the uncertainty set and the probability measure are both symmetric. However, we prove that the adaptability gap (ratio of optimal cost of the robust problem and the optimal cost of a twostage fullyadaptable problem) is at most four even if both the objective coefficients and the right hand side of the constraints are uncertain and belong to a symmetric uncertainty set. The bound holds for the class of {\em positive} uncertainty sets as well. Moreover, if the uncertainty set is a hypercube (special case of a symmetric set), the adaptability gap is one under an even more general model of uncertainty where the constraint coefficients are also uncertain. Keywords: robust optimization, stochastic optimization, adaptive optimization, stochasticity gap, adaptability gap Category 1: Robust Optimization Category 2: Stochastic Programming Citation: Operations Research Center, MIT (June 2009) Download: [PDF] Entry Submitted: 09/04/2009 Modify/Update this entry  
Visitors  Authors  More about us  Links  
Subscribe, Unsubscribe Digest Archive Search, Browse the Repository

Submit Update Policies 
Coordinator's Board Classification Scheme Credits Give us feedback 
Optimization Journals, Sites, Societies  