Optimization Online


Finitely Convergent Decomposition Algorithms for Two-Stage Stochastic Pure Integer Programs

Minjiao Zhang (zhang.769***at***osu.edu)
Simge Küçükyavuz (kucukyavuz.2***at***osu.edu)

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.

Keywords: Two-stage stochastic pure integer programs, Gomory cuts, Benders' decomposition

Category 1: Integer Programming

Category 2: Stochastic Programming

Citation: Technical Report, Department of Integrated Systems Engineering, The Ohio State University

Download: [PDF]

Entry Submitted: 06/27/2013
Entry Accepted: 06/28/2013
Entry Last Modified: 05/07/2014

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