Cutting Planes for Multistage Stochastic Integer Programs

Yongpei Guan, Shabbir Ahmed, George L. Nemhauser

Operations Research · 2009 · Volume 57 · Issue 2

Abstract

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.

Keywords

programming, integer, cutting plane/facet, programming, stochastic, inventory/production, lot sizing, stochastic

Enable JavaScript for citation tools and additional paper interactions.