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

46 Scopus citations


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
Issue number1-2
StatePublished - Apr 2014


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

ASJC Scopus subject areas

  • Software
  • Mathematics(all)


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