Cutting Planes for Multistage Stochastic Integer Programs
成果类型：
Article
署名作者：
Guan, Yongpei; Ahmed, Shabbir; Nemhauser, George L.
署名单位：
University of Oklahoma System; University of Oklahoma - Norman; University System of Georgia; Georgia Institute of Technology
刊物名称：
OPERATIONS RESEARCH
ISSN/ISSBN：
0030-364X
DOI：
10.1287/opre.1080.0535
发表日期：
2009
页码：
287-298
关键词：
摘要：
This paper addresses the problem of finding cutting planes for multistage stochastic integer programs. We give a general method for generating cutting planes for multistage stochastic integer programs based on combining inequalities that are valid for the individual scenarios. We apply the method to generate cuts for a stochastic version of a dynamic knapsack problem and for stochastic lot-sizing problems. We give computational results, which show that these new inequalities are very effective in a branch-and-cut algorithm.