The Benders decomposition algorithm: A literature review

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. (C)2016 Elsevier B.V. All rights reserved.

本德斯分解算法已成功应用于一系列困难的优化问题。本文对该算法进行了最新的综述，强调其在组合优化中的应用。我们讨论了经典算法、问题表述对其收敛性的影响以及与其他分解方法的关系。我们基于算法的主要组成部分引入了一种算法增强和加速策略的分类法。这种分类法为综合文献以及确定不足、趋势和潜在研究方向提供了框架。我们还讨论了使用本德斯分解来开发高效（元）启发式算法，描述了经典算法的局限性，并介绍了使其能够应用于更广泛问题的扩展。©2016爱思唯尔有限公司。保留所有权利。