Strengthened Benders Cuts for Stochastic Integer Programs with Continuous Recourse

Merve Bodur (), Sanjeeb Dash (), Oktay Günlük () and James Luedtke ()
Additional contact information
Merve Bodur: Department of Mechanical and Industrial Engineering, University of Toronto, Toronto, Ontario M5S 3G8, Canada
Sanjeeb Dash: Mathematical Sciences Department, IBM T.J. Watson Research Center, Yorktown Heights, New York 10598
Oktay Günlük: Mathematical Sciences Department, IBM T.J. Watson Research Center, Yorktown Heights, New York 10598
James Luedtke: Department of Industrial and Systems Engineering, University of Wisconsin-Madison, Madison, Wisconsin 53706

INFORMS Journal on Computing, 2017, vol. 29, issue 1, 77-91

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 (search for similar items in EconPapers)
Date: 2017
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (16)

Downloads: (external link)
https://doi.org/10.1287/ijoc.2016.0717 (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:inm:orijoc:v:29:y:2017:i:1:p:77-91

Access Statistics for this article

More articles in INFORMS Journal on Computing from INFORMS Contact information at EDIRC.
Bibliographic data for series maintained by Chris Asher ().