Portal de Periódicos da CAPES

The Benders decomposition algorithm: A literature review

2016; Elsevier BV; Volume: 259; Issue: 3 Linguagem: Inglês

10.1016/j.ejor.2016.12.005

1872-6860

Ragheb Rahmaniani, Teodor Gabriel Crainic, Michel Gendreau, Walter Rei,

Constraint Satisfaction and Optimization

The Benders decomposition algorithm has been successfully applied to a wide range of difficult optimization problems. This paper presents a state-of-the-art survey of this algorithm, emphasizing its use in combinatorial optimization. We discuss the classical algorithm, the impact of the problem formulation on its convergence, and the relationship to other decomposition methods. We introduce a taxonomy of algorithmic enhancements and acceleration strategies based on the main components of the algorithm. The taxonomy provides the framework to synthesize the literature, and to identify shortcomings, trends and potential research directions. We also discuss the use of the Benders Decomposition to develop efficient (meta-)heuristics, describe the limitations of the classical algorithm, and present extensions enabling its application to a broader range of problems.