Cutting planes for multi-stage stochastic integer programs

Yongpei Guan (yguanou.edu)
Shabbir Ahmed (sahmedgatech.edu)
George L. Nemhauser (nemhausisye.gatech.edu)

Abstract: This paper addresses the problem of finding cutting planes for multi-stage stochastic integer programs. We give a general method for generating cutting planes for multi-stage 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 to stochastic lot sizing problems. We give computational results which show that these new inequalities are very effective in a branch-and-cut algorithm.

Keywords: stochastic integer programming, branch-and-cut, stochastic lot-sizing, stochastic dynamic knapsack

Category 1: Stochastic Programming

Category 2: Integer Programming (Cutting Plane Approaches )

Citation:

Download: [PDF]

Entry Submitted: 09/15/2006
Entry Accepted: 09/15/2006
Entry Last Modified: 09/15/2006

Modify/Update this entry