Finitely convergent decomposition algorithms for two-stage stochastic pure integer programs

Minjiao Zhang, Simge Kucukyavuz

Research output: Contribution to journalArticle

20 Scopus citations

Abstract

We study a class of two-stage stochastic integer programs with general integer variables in both stages and finitely many realizations of the uncertain parameters. Based on Benders' method, we propose a decomposition algorithm that utilizes Gomory cuts in both stages. The Gomory cuts for the second-stage scenario subproblems are parameterized by the first-stage decision variables, i.e., they are valid for any feasible first-stage solutions. In addition, we propose an alternative implementation that incorporates Benders' decomposition into a branch-and-cut process in the first stage. We prove the finite convergence of the proposed algorithms. We also report our preliminary computations with a rudimentary implementation of our algorithms to illustrate their effectiveness.

Original languageEnglish (US)
Pages (from-to)1933-1951
Number of pages19
JournalSIAM Journal on Optimization
Volume24
Issue number4
DOIs
StatePublished - Jan 1 2014

Keywords

  • Benders' decomposition
  • Gomory cuts
  • Two-stage stochastic pure integer programs

ASJC Scopus subject areas

  • Software
  • Theoretical Computer Science

Fingerprint Dive into the research topics of 'Finitely convergent decomposition algorithms for two-stage stochastic pure integer programs'. Together they form a unique fingerprint.

  • Cite this