Accelerating Benders Decomposition by Local Branching
Walter Rei, Jean-François Cordeau, Michel Gendreau, Patrick Soriano
INFORMS Journal on Computing · 2009 · Volume 21 · Issue 2
Abstract
This paper shows how local branching can be used to accelerate the classical Benders decomposition algorithm. By applying local branching throughout the solution process, one can simultaneously improve both the lower and upper bounds. We also show how Benders feasibility cuts can be strengthened or replaced with local branching constraints. To assess the performance of the different algorithmic ideas presented in this hybrid solution approach, extensive computational experiments were performed on two families of network design problems. Numerical results clearly illustrate their benefits.
Keywords
Benders decomposition, local branching, deterministic and stochastic network design, hybrid solution approach
Enable JavaScript for citation tools and additional paper interactions.