Implementing the branch-and-cut approach for a general purpose Benders’ decomposition framework
| Autor: | Stephen J. Maher |
|---|---|
| Rok vydání: | 2021 |
| Předmět: |
Flexibility (engineering)
050210 logistics & transportation Mathematical optimization 021103 operations research Information Systems and Management General Computer Science Computer science business.industry 05 social sciences 0211 other engineering and technologies 02 engineering and technology Management Science and Operations Research Solver Industrial and Manufacturing Engineering Constraint (information theory) Software Modeling and Simulation 0502 economics and business Constraint programming Decomposition (computer science) Computer Science::Symbolic Computation business Branch and cut Integer programming |
| Zdroj: | European Journal of Operational Research. 290:479-498 |
| ISSN: | 0377-2217 |
| Popis: | 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. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|
Full Text from ScienceDirect