Optimization Online


Strengthened Benders Cuts for Stochastic Integer Programs with Continuous Recourse

Merve Bodur (mbodur***at***wisc.edu)
Sanjeeb Dash (sanjeebd***at***us.ibm.com)
Oktay Gunluk (gunluk***at***us.ibm.com)
James Luedtke (jrluedt1***at***wisc.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.

Download: [PDF]

Entry Submitted: 03/02/2014
Entry Accepted: 03/02/2014
Entry Last Modified: 04/10/2017

Modify/Update this entry

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Optimization Society