This Article Full Text (PDF) References Alert me when this article is cited Alert me if a correction is posted Services Email this article to a friend Similar articles in this journal Alert me to new issues of the journal Download to citation manager Citing Articles Citing Articles via Google Scholar Google Scholar Articles by Guan, Y. Articles by Nemhauser, G. L. Search for Related Content

Cutting Planes for Multistage Stochastic Integer Programs

School of Industrial Engineering, University of Oklahoma, Norman, Oklahoma 73019
H. Milton Stewart School of Industrial and Systems Engineering, Georgia Institute of Technology, Atlanta, Georgia 30332
H. Milton Stewart School of Industrial and Systems Engineering, Georgia Institute of Technology, Atlanta, Georgia 30332
yguan{at}ou.edu
sahmed{at}isye.gatech.edu
gnemhaus{at}isye.gatech.edu

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.

Subject classifications: programming; integer; cutting plane/facet; programming; stochastic; inventory/production; lot sizing; stochastic.
History: Received September 2006; revision received October 2007; accepted November 2007.