Strengthened Benders Cuts for Stochastic Integer Programs with Continuous Recourse

Strengthened Benders Cuts for Stochastic Integer Programs with Continuous Recourse

0.00 Avg rating0 Votes
Article ID: iaor20165096
Volume: 29
Issue: 1
Start Page Number: 77
End Page Number: 91
Publication Date: Feb 2017
Journal: INFORMS Journal on Computing
Authors: , , ,
Keywords: programming: integer, heuristics, stochastic processes
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.

Reviews

Required fields are marked *. Your email address will not be published.