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. |
Year | DOI | Venue |
---|---|---|
2017 | 10.1287/ijoc.2016.0717 | INFORMS JOURNAL ON COMPUTING |
Keywords | Field | DocType |
two-stage stochastic integer programs, Benders decomposition, split cuts | Integer,Discrete mathematics,Mathematical optimization,Stochastic integer programming,Benders' decomposition,Mathematics | Journal |
Volume | Issue | ISSN |
29 | 1 | 1091-9856 |
Citations | PageRank | References |
12 | 0.52 | 16 |
Authors | ||
4 |
Name | Order | Citations | PageRank |
---|---|---|---|
Merve Bodur | 1 | 32 | 3.89 |
Sanjeeb Dash | 2 | 448 | 32.93 |
Oktay GüNlüK | 3 | 502 | 41.29 |
James Luedtke | 4 | 439 | 25.95 |