Finitely Convergent Decomposition Algorithms for Two-Stage Stochastic Pure Integer ProgramsSIAM Journal on Optimization (2014)
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 8 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.
- Two-stage stochastic pure integer programs,
- Gomory cuts,
- Benders’ decomposition
Citation InformationMinjiao Zhang and Simge Kucukyavuz. "Finitely Convergent Decomposition Algorithms for Two-Stage Stochastic Pure Integer Programs" SIAM Journal on Optimization (2014)
Available at: http://works.bepress.com/minjiaozhang/3/