Strengthened Benders Cuts for Stochastic Integer Programs with Continuous Recourse
Merve Bodur (mbodurwisc.edu)
Abstract: With stochastic integer programming as the motivating application, we investigate techniques to use integrality constraints to obtain improved cuts within a Benders decomposition algorithm. We compare the effect of using cuts in two ways: (i) cut-and-project, where integrality constraints are used to derive cuts in the extended variable space, and Benders cuts are then used to project the resulting improved relaxation, and (ii) project-and-cut, where integrality constraints are used to derive cuts directly in the Benders reformulation. For the case of split cuts, we demonstrate that although these approaches yield equivalent relaxations when considering a single split disjunction, cut-and-project yields stronger relaxations in general when using multiple split disjunctions. Computational results illustrate that the difference can be very large, and demonstrate that using split cuts within the cut-and-project framework can significantly improve the performance of Benders decomposition.
Keywords: Two-stage stochastic integer programs, Benders decomposition, Split cuts
Category 1: Stochastic Programming
Category 2: Integer Programming (Cutting Plane Approaches )
Category 3: Integer Programming ((Mixed) Integer Linear Programming )
Citation: University of Wisconsin-Madison, IBM Research, March, 2014.
Entry Submitted: 03/02/2014
Modify/Update this entry
|Visitors||Authors||More about us||Links|
Search, Browse the Repository
Give us feedback
|Optimization Journals, Sites, Societies|