Decomposition algorithms with parametric Gomory cuts for two-stage stochastic integer programs

• 成果类型: Article
• 署名作者: Gade, Dinakar; Kuecuekyavuz, Simge; Sen, Suvrajeet
• 署名单位: University System of Ohio; Ohio State University
• 刊物名称: MATHEMATICAL PROGRAMMING
• ISSN/ISSBN: 0025-5610
• DOI: 10.1007/s10107-012-0615-y
• 发表日期: 2014
• 页码: 39-64
• 关键词: branch

摘要

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 -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.