Manual

Motivation

Benders Decomposition is a powerful mathematical programming technique for optimization problems with block structure, developed by Jacques Benders (1941-2017) in 1962 [1]. The method decomposes a complex problem into smaller, more manageable master problem and subproblem, which can be solved iteratively to find the optimal solution to the original problem.

        xychart-beta
  title "Benders Decomposition Publications"
  x-axis "Year" 2000 --> 2025
  y-axis "Number of Papers"
  bar [8, 14, 9, 11, 16, 30, 29, 38, 47, 60, 44, 50, 66, 102, 86, 119, 147, 181, 201, 231, 229, 309, 273, 242, 295, 359]
    

*Interesting fact: In 2025, 359 papers using Benders decomposition were published, averaging nearly one per day.

From 1962 to 2025, there are many research articles on Benders Decomposition, covering a wide range of applications in various fields, including supply chain management, energy systems, transportation, finance, and many others. Despite its popularity and wide applicability, there is no software library specializing in Benders Decomposition and its variants. This project aims to fill this gap by providing a user-friendly and extensible library for Benders Decomposition - BendersLib, which can be easily integrated with existing optimization solvers and frameworks. Although this library is designed to be extended with user-defined Benders cuts, acceleration techniques, and algorithms, it also implements several representative Benders Decomposition variants for rapid prototyping and benchmarking.

What can BendersLib provide?

BendersLib offers a flexible and powerful framework for implementing Benders decomposition. Here’s what you can do with it.

• Rapid Prototyping: BendersLib implements several common Benders decomposition algorithms. It also includes various built-in Benders cuts, enabling users to quickly prototype and validate their models. This allows researchers and practitioners to quickly test the feasibility of a Benders decomposition approach for their specific problem without implementing the entire algorithm from scratch. It significantly reduces development time and lowers the barrier to entry for using this technique.

• High Extensibility: BendersLib is highly extensible. Users can easily customize core components like solver interfaces, LogicBasedSubProblem, and CutGenerator to meet their specific needs. This flexibility is crucial for tackling complex, real-world problems that may require non-standard decomposition structures or specialized cut generation strategies. It empowers users to tailor the framework to their unique problem, facilitating research into new Benders variants and acceleration techniques.

What cannot BendersLib do?

While BendersLib is a powerful tool, it’s important to understand its scope.

• It cannot automatically identify complicating variables. BendersLib requires the user to define which variables are part of the master problem and which belong to the subproblem. This decision is problem-specific and is a critical step in the modeling process that relies on the user’s domain knowledge and understanding of the problem structure. The library (currently) does not have the capability to analyze a model and suggest a decomposition.

• It does not guarantee performance improvements. The effectiveness of Benders decomposition is highly dependent on the structure of the problem. While it can lead to performance gains for certain classes of problems, it is not a silver bullet. For some problems, the computational overhead of managing the master problems, subproblems, and Benders cuts can exceed the benefits of decomposition, leading to longer solution times compared to solving the monolithic problem.

• It is not a standalone solver. You still need to formulate your optimization problem using a dedicated modeling library. BendersLib orchestrates the decomposition and solution process, but it does not solve master problems or subproblems on its own. You must integrate it with an appropriate solver interface that can handle your specific problem type.

Alternatives

Several optimization solvers overlap with BendersLib’s functionality. Consider one of these alternatives if BendersLib does not meet your requirements. Here we only present actively maintained ones, see our paper for a comprehensive comparison.

Optimization Solvers with Benders Decomposition Features

Name	Feature	Language	License
AIMMS	An optimization modeling system that supports automatic Benders decomposition.	AIMMS Language	Commercial
Coluna.jl	A branch-and-price-and-cut framework that supports Benders Decomposition.	Julia	MPL 2.0
CPLEX	An optimization solver that supports annotated Benders decomposition [2].	C/C++, Java, .NET	Commercial
DECIS	A solver for stochastic programming that supports L-shaped method.	GAMS Language	Commercial
FortSP	A solver for stochastic programming that supports (integer) L-shaped method and nested Benders decomposition.	C	Commercial
GCG	A generic decomposition solver for mixed-integer programs that has the capability of automatically Benders decomposition (part of the SCIP Optimization Suit).	C/C++ *	LGPL
mpi-sppy	A package for solving Stochastic Programming problems with L-shaped method and other decomposition algorithms.	Python	BSD 3 Clause
SCIP	A framework for constraint integer programming and branch-cut-and-price that supports Benders Decomposition [3].	C/C++ *	Apache 2.0
SAS	An analytics software suite that supports Benders decomposition.	SAS Language	Commercial
SDDP.jl [4]	A package for solving Multistage Stochastic Programming using Stochastic Dual Dynamic Programming (nested Benders methods).	Julia	MPL 2.0
SMS++	A modeling system for modeling complex block-structured mathematical models.	C++	LGPL 3.0
StochasticPrograms.jl [5]	A package for modeling and solving Stochastic Programming problems that supports the L-shaped method.	Julia	MIT License

* Note: SCIP has a Python interface namely PySCIPOpt; GCG has a Python interface namely PyGCGOpt.

Contents

• Installation
  • Installing BendersLib
    • Environment Setup (optional)
    • Installing BendersLib
    • Verifying the Installation
  • Installing Solvers
  • Troubleshooting
• Quickstart
  • Is Benders Decomposition suitable for your problem?
  • Step-by-Step Guide
    • Step 1: Building the Master Problem
    • Step 2: Building the Subproblem
    • Step 3: Building the Benders Decomposition Instance
    • Step 4: Solving the Instance
  • Conventions
  • References
• Components
  • Overview of the Design
  • Main Components
• Workflow
  • Basic Usage
  • Advanced Usage
  • Expert Usage
• Solver Interfaces
  • Supported Solvers
  • Customization
  • Attributes & Methods
• Master Problem
  • Create a Master Problem
    • COPT
    • CPLEX
    • Gurobi
    • Pyomo
    • SCIP
  • Create a Master Problem from an Annotated Model
  • Add Benders Cuts to Master Problem
  • Access and Remove Cuts
  • Solve and Access Results
  • Attributes & Methods
• Subproblem
  • Create a Subproblem
    • COPT
    • CPLEX
    • Gurobi
    • Pyomo
    • SCIP
    • OR-Tools (Constraint Programming)
    • Cplex (Constraint Programming)
  • Create a Subproblem from an Annotated Model
  • Compute Irreducible Infeasible Subsystem (IIS)
  • Create Multiple Subproblems
  • Solve and Access Results
  • Customization
    • Custom Subproblem (class-based)
    • Custom Subproblem (function-based)
    • Multiple Custom Subproblems (class-based)
    • Multiple Custom Subproblems (function-based)
  • Attributes & Methods
• Benders Cut
  • Cut
  • Cut Generator
  • Customization
    • Custom Benders Cut
    • Custom Cut Generator (class-based)
    • Custom Cut Generator (function-based)
  • Attributes & Methods
• Benders Methods
  • Create a Benders Decomposition Instance
  • Options for Benders Decomposition
  • Solve the Benders Decomposition Instance
  • Access Additional Statistics
  • Automated Decomposition
  • Customization
  • Attributes & Methods
• Callbacks
  • What are Callbacks?
  • How to Use Callbacks?
  • Registering Multiple Callbacks
  • Attributes & Methods
• Logging and Profiling
  • Understanding the Log
  • Profiling
• Numerical Issues
  • Comparing Objective Function Values
  • Determining Whether Two Cuts are Identical
  • Handling Large Cutting Coefficients
• How-To Guides
  • How to access to attributes not listed in the API reference?
  • How to build master/sub problems from a monolithic model?
  • How to start from standard mathematical programming files?
• Contributing
  • Development Workflow
  • Guidelines
    • Contributing a Solver Interface
    • Contributing a Benders Method Implementation

References

[1]

Benders, J. F. (1962). Partitioning procedures for solving mixed-variables programming problems. Numerische Mathematik, 4(1), 238–252. https://doi.org/10.1007/BF01386316

[2]

Bonami, P., Salvagnin, D., & Tramontani, A. (2020). Implementing Automatic Benders Decomposition in a Modern MIP Solver. In D. Bienstock & G. Zambelli (Eds.), Integer Programming and Combinatorial Optimization (pp. 78–90). Springer International Publishing. https://doi.org/10.1007/978-3-030-45771-6_7

[3]

Maher, S. J. (2021). Implementing the branch-and-cut approach for a general purpose Benders’ decomposition framework. European Journal of Operational Research, 290(2), 479–498. https://doi.org/10.1016/j.ejor.2020.08.037

[4]

Dowson, O., & Kapelevich, L. (2021). SDDP.jl: A Julia Package for Stochastic Dual Dynamic Programming. INFORMS Journal on Computing, 33(1), 27–33. https://doi.org/10.1287/ijoc.2020.0987

[5]

Biel, M., & Johansson, M. (2022). Efficient Stochastic Programming in Julia. INFORMS Journal on Computing, 34(4), 1885–1902. https://doi.org/10.1287/ijoc.2022.1158