Optimization Online


Decomposition Algorithms for Two-Stage Distributionally Robust Mixed Binary Programs

Manish Bansal (bansal***at***vt.edu)
Kuo-Ling Huang (jupiters1117***at***northwestern.edu)
Sanjay Mehrotra (mehrotra***at***northwestern.edu)

Abstract: In this paper, we introduce and study a two-stage distributionally robust mixed binary problem (TSDR-MBP) where the random parameters follow the worst-case 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 L-shaped method, to solve TSDR-MBPs 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) L-shaped 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 Kantorovich-Rubinstein distance (Wasserstein metric), which satisfy the foregoing conditions. We also present a cutting surface algorithm to solve TSDR-MBPs. We computationally evaluate the performance of the DRI L-shaped 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 two-stage stochastic optimization problems.

Keywords: Distributionally robust optimization; two-stage stochastic mixed binary programs; Benders' decomposition; L-shaped method; ambiguity set; parametric cutting planes; moment matching; Kantorovich-Rubinstein distance; Wasserstein metric

Category 1: Robust Optimization

Category 2: Stochastic Programming

Category 3: Integer Programming (0-1 Programming )

Citation: M. Bansal, K. L. Huang, and S. Mehrotra, "Decomposition algorithms for two-stage distributionally robust mixed binary programs," SIAM Journal on Optimization, 28(3), 23602383, 2018. [https://epubs.siam.org/doi/abs/10.1137/17M1115046]


Entry Submitted: 02/07/2017
Entry Accepted: 02/07/2017
Entry Last Modified: 09/01/2018

Modify/Update this entry

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Optimization Society