Optimization Online


Implementing the branch-and-cut approach for a general purpose Benders' decomposition framework

Stephen J Maher (s.j.maher***at***exeter.ac.uk)

Abstract: 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.

Keywords: Benders' decomposition, branch-and-cut, mixed integer programming, constraint integer programming, optimisation software

Category 1: Integer Programming

Category 2: Optimization Software and Modeling Systems

Citation: University of Exeter, September 2019

Download: [PDF]

Entry Submitted: 09/24/2019
Entry Accepted: 09/24/2019
Entry Last Modified: 09/25/2019

Modify/Update this entry

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Optimization Society