Optimization Online


Decomposition Algorithms with Parametric Gomory Cuts for Two-Stage Stochastic Integer Programs

Dinakar Gade (gade.6***at***osu.edu)
Simge Kucukyavuz (kucukyavuz.2***at***osu.edu)
Suvrajeet Sen (sen.22***at***osu.edu)

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.

Keywords: Two-stage stochastic integer programs, Gomory cuts, L-Shaped method, Benders decomposition, Lexicographic dual simplex, finite convergence

Category 1: Stochastic Programming

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

Download: [PDF]

Entry Submitted: 02/23/2012
Entry Accepted: 02/23/2012
Entry Last Modified: 08/15/2012

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