  


Decomposition Algorithms for TwoStage Distributionally Robust Mixed Binary Programs
Manish Bansal (bansalvt.edu) Abstract: In this paper, we introduce and study a twostage distributionally robust mixed binary problem (TSDRMBP) where the random parameters follow the worstcase distribution belonging to an uncertainty set of probability distributions. We present a decomposition algorithm, which utilizes distribution separation procedure and parametric cuts within Benders' algorithm or Lshaped method, to solve TSDRMBPs with binary variables in the first stage and mixed binary programs in the second stage. We refer to this algorithm as distributionally robust integer (DRI) Lshaped algorithm. Using similar decomposition framework, we provide another algorithm to solve TSDR linear problem where both stages have only continuous variables. We investigate conditions and the families of ambiguity set for which our algorithms are finitely convergent. We present two examples of ambiguity set, defined using moment matching, or KantorovichRubinstein distance (Wasserstein metric), which satisfy the foregoing conditions. We also present a cutting surface algorithm to solve TSDRMBPs. We computationally evaluate the performance of the DRI Lshaped algorithm and the cutting surface algorithm in solving distributionally robust versions of a few instances from the Stochastic Integer Programming Library, in particular stochastic server location and stochastic multiple binary knapsack problem instances. We also discuss the usefulness of incorporating partial distribution information in twostage stochastic optimization problems. Keywords: Distributionally robust optimization; twostage stochastic mixed binary programs; Benders' decomposition; Lshaped method; ambiguity set; parametric cutting planes; moment matching; KantorovichRubinstein distance; Wasserstein metric Category 1: Robust Optimization Category 2: Stochastic Programming Category 3: Integer Programming (01 Programming ) Citation: M. Bansal, K. L. Huang, and S. Mehrotra, "Decomposition algorithms for twostage distributionally robust mixed binary programs," SIAM Journal on Optimization (Forthcoming), 2018. Download: [PDF] Entry Submitted: 02/07/2017 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  