Decomposition algorithms with parametric Gomory cuts for two-stage stochastic integer programs

Dinakar Gade, Simge Küçükyavuz*, Suvrajeet Sen

*Corresponding author for this work

Research output: Contribution to journalArticlepeer-review

31 Scopus citations

Abstract

We consider a class of two-stage stochastic integer programs with binary variables in the first stage and general integer variables in the second stage. We develop decomposition algorithms akin to the L -shaped or Benders' methods by utilizing Gomory cuts to obtain iteratively tighter approximations of the second-stage integer programs. We show that the proposed methodology is flexible in that it allows several modes of implementation, all of which lead to finitely convergent algorithms. We illustrate our algorithms using examples from the literature. We report computational results using the stochastic server location problem instances which suggest that our decomposition-based approach scales better with increases in the number of scenarios than a state-of-the art solver which was used to solve the deterministic equivalent formulation.

Original languageEnglish (US)
Pages (from-to)39-64
Number of pages26
JournalMathematical Programming
Volume144
Issue number1-2
DOIs
StatePublished - Apr 2014

Keywords

  • Benders' decomposition
  • Finite convergence
  • Gomory cuts
  • L -shaped method
  • Lexicographic dual simplex
  • Two-stage stochastic integer programs

ASJC Scopus subject areas

  • Software
  • Mathematics(all)

Fingerprint Dive into the research topics of 'Decomposition algorithms with parametric Gomory cuts for two-stage stochastic integer programs'. Together they form a unique fingerprint.

Cite this