This Article Full Text (PDF) References Alert me when this article is cited Alert me if a correction is posted Services Email this article to a friend Similar articles in this journal Alert me to new issues of the journal Download to citation manager Citing Articles Citing Articles via Google Scholar Google Scholar Articles by Rei, W. Articles by Soriano, P. Search for Related Content

Accelerating Benders Decomposition by Local Branching

Département de management et de technologie, ESG, UQÀM, Montréal, Québec H3C 3P8, Canada, and CIRRELT, Montréal, Québec H3C 3J7, Canada
Service de l'enseignement de la gestion des opérations et de la logistique, HEC Montréal, Montréal, Québec H3T 2A7, Canada, and CIRRELT, Montréal, Québec H3C 3J7, Canada
Département d'informatique et de recherche opérationnelle, Université de Montréal, Montréal, Québec H3C 3J7, Canada, and CIRRELT, Montréal, Québec H3C 3J7, Canada
Service de l'enseignement des méthodes quantitatives de gestion, HEC Montréal, Montréal, Québec H3T 2A7, Canada, and CIRRELT, Montréal, Québec H3C 3J7, Canada
rei.walter{at}uqam.ca
jean-francois.cordeau{at}hec.ca
michel.gendreau{at}cirrelt.ca
patrick.soriano{at}hec.ca

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.

Key words: Benders decomposition; local branching; deterministic and stochastic network design; hybrid solution approach
History: received November 2006; revised June 2008; accepted June 2008.