Decomposition algorithms for two-stage distributionally robust mixed binary programs

Manish Bansal*, Kuo Ling Huang, Sanjay Mehrotra

*Corresponding author for this work

Research output: Contribution to journalArticlepeer-review

8 Scopus citations

Abstract

In this paper, we introduce and study a two-stage distributionally robust mixedbinary problem (TSDR-MBP) in which the random parameters follow the worst-case distributionbelonging to an uncertainty set of probability distributions. We present a decomposition algorithm,which utilizes a distribution separation procedure and parametric cuts within Benders' algorithmor the L-shaped method, to solve TSDR-MBPs with binary variables in the first stage and mixedbinary programs in the second stage. We refer to this algorithm as a distributionally robust integer(DRI) L-shaped algorithm. Using a similar decomposition framework, we provide another algorithmto solve a TSDR linear problem where both stages have only continuous variables. We investigate conditions and the families of ambiguity sets for which our algorithms are finitely convergent.We present two examples of ambiguity set, defined using moment matching or the Kantorovich{Rubinstein distance (Wasserstein metric), which satisfy the foregoing conditions. We also present acutting surface algorithm to solve TSDR-MBPs. We computationally evaluate the performance of theDRI L-shaped algorithm and the cutting surface algorithm in solving distributionally robust versionsof a few instances from the stochastic integer programming library, in particular stochastic serverlocation and stochastic multiple binary knapsack problem instances. We also discuss the usefulnessof incorporating partial distribution information in two-stage stochastic optimization problems.

Original languageEnglish (US)
Pages (from-to)2360-2383
Number of pages24
JournalSIAM Journal on Optimization
Volume28
Issue number3
DOIs
StatePublished - 2018

Keywords

  • Ambiguity set
  • Benders' decomposition
  • Distributionally robust optimization
  • Kantorovich{Rubinstein distance
  • L-shaped Method
  • Two-stage stochastic mixed binary programs
  • Wasserstein metric
  • moment matching
  • parametric cutting planes

ASJC Scopus subject areas

  • Software
  • Theoretical Computer Science

Fingerprint Dive into the research topics of 'Decomposition algorithms for two-stage distributionally robust mixed binary programs'. Together they form a unique fingerprint.

Cite this