Implementing the branch-and-cut approach for a general purpose Benders' decomposition framework
Implementing the branch-and-cut approach for a general purpose Benders' decomposition framework
复制标题
DOI：
10.1016/j.ejor.2020.08.037
复制
发表时间：
2021-04-16
影响因子：
6.4
通讯作者：
Maher, Stephen J.
中科院分区：
文献类型：
--
作者：
Maher, Stephen J.
Benders分解是一种流行的数学和约束规划算法，被广泛应用于求解实际应用中的问题结构。虽然对于利用数学和约束程序中的结构很有用，但使用bender分解通常需要大量的实现工作来实现有效的解决算法。传统上，Benders分解被看作是一种特定问题的算法，这限制了通用算法和软件解决方案的发展。本文提出了一种通用的Benders分解算法，它能够处理许多类型的数学和约束程序，并在该算法的实现和使用中提供了广泛的灵活性。在约束整数规划求解器SCIP中实现了Benders分解的分支切断方法，该方法使用基于插件的设计，允许对算法进行各种扩展和定制。在全面的计算研究中，评估了Benders分解算法和可用增强技术的有效性。(C) 2020 Elsevier B.V.版权所有
Benders' decomposition is a popular mathematical and constraint programming algorithm that is widely applied to exploit problem structure arising from real-world applications. While useful for exploiting structure in mathematical and constraint programs, the use of Benders' decomposition typically requires significant implementation effort to achieve an effective solution algorithm. Traditionally, Benders' decomposition has been viewed as a problem specific algorithm, which has limited the development of general purpose algorithms and software solutions. This paper presents a general purpose Benders' decomposition algorithm that is capable of handling many classes of mathematical and constraint programs and provides extensive flexibility in the implementation and use of this algorithm. A branch-and-cut approach for Benders' decomposition has been implemented within the constraint integer programming solver SCIP using a plugin-based design to allow for a wide variety of extensions and customisations to the algorithm. The effectiveness of the Benders' decomposition algorithm and available enhancement techniques is assessed in a comprehensive computational study. (C) 2020 Elsevier B.V. All rights reserved.