Tutorials¶
This tutorial section offers an overview of the Benders Decomposition theory, covering its development over more than fifty years. There are several important variants of Benders Decomposition listed below. They are implemented (Benders Methods, Examples) in BendersLib, and these representative variants will help guide the design (Manual, API Reference) of the library.
Name |
P. Type |
M.P. Type |
S.P. Type |
|---|---|---|---|
(Classical) Benders Decomposition [1] |
MILP |
MILP |
LP |
Combinatorial Benders Decomposition [2] |
MILP |
MILP |
Feasibility |
Generalized Benders Decomposition [3] |
NLP |
NLP |
Convex NLP |
L-shaped Method [4] |
Stochastic LP |
LP |
LP |
Integer L-shaped Method [5] |
Stochastic MILP |
MILP (binary) |
MILP (binary) |
Logic-based Benders Decomposition [6] |
Any |
Any |
Any |
P.: Original problem, M.P.: Master problem, S.P.: Sub problem, MILP: Mixed-Integer Linear Programming, LP: Linear Programming, NLP: Non-Linear Programming.
A Benders Decomposition method is composed of a master problem, one or more subproblems, Benders cuts, and a Benders algorithm that orchestrates the solution process, to solve the original mathematical programming problem. These components make one Benders method different from another. A brief introduction of the components of these variants is given below.
Classical Benders Decomposition is essentially a Kelley’s cutting-plane method [7] for solving MILPs. It works by splitting a problem into two parts: a master problem that handles the difficult (integer) decisions and a subproblem that deals with the consequences of those decisions. The master problem, an MILP, proposes a set of integer variables, and the subproblem, a much simpler LP, checks the feasibility and optimality of that proposal. Information from the subproblem’s dual solution is then used to generate linear Benders optimality cuts and Benders feasibility cuts that are added to the master problem, systematically refining the solution until an optimum is found.
Combinatorial Benders Decomposition extends the cutting-plane approach to MILPs where the subproblem is itself a combinatorial problem, typically a MILP. Like the classical method, it divides the problem into a master problem and a subproblem that assesses the consequences, based on pure binary complicating variables. The fundamental difference is that the subproblem is not a simple LP, meaning its solution does not provide the dual information used in classical Benders. Instead, cuts are generated through combinatorial arguments: no-good cuts are derived from proofs of subproblem infeasibility, while combinatorial optimality cuts are logical constraints that connect a specific set of master decisions to the resulting subproblem cost.
Generalized Benders Decomposition is an extension of the classical method to solve convex NLPs. It partitions the problem based on variable type, where the master problem handles complicating variables and the subproblem solves a convex NLP for fixed values of these variables. The key is the use of nonlinear duality theory to generate cutting planes, known as Lagrangian cuts, that approximate the subproblem’s objective function.
L-shaped Method is a specialized version of Benders Decomposition for Stochastic Linear Programming problems. The first-stage decisions (master problem) are made before uncertainty is resolved, and the second-stage decisions (subproblem) adapt to the outcomes. The method iteratively adds optimality cuts (for expected future costs) and feasibility cuts (to handle scenarios where second-stage constraints cannot be met) to the master problem, refining the first-stage decision until an optimal solution is found. It can be seen as a specific application of Classical Benders Decomposition to Stochastic Programming.
Integer L-shaped Method adapts the L-shaped method for stochastic programs where some decision variables in the second stage are integers. This introduces non-convexity, so linear programming duality cannot be directly applied. Instead, the integer L-shaped method can be seen as a combination of L-shaped Method and Combinatorial Benders Decomposition. The cuts are derived from the structure of the integer subproblem, often using no-good cuts to exclude infeasible first-stage decisions and combinatorial optimality cuts to capture the cost implications of specific first-stage decisions.
Logic-based Benders Decomposition is a framework that combines Benders Decomposition with logic-based methods (e.g., Constraint Programming). It is highly flexible and can be applied to a wide range of optimization problems. The master problem provides a partial assignment of variables, and the subproblem, determines the consequences. Instead of relying on traditional duality, LBDD uses inference and combinatorial arguments to generate cuts. For example, if a subproblem is infeasible, a no-good cut is generated to exclude that specific assignment of master variables.
See also
A review of Benders Decomposition by Rahmaniani et al. [8].
A review of Jacques Benders’ life and work by Aardal et al. [9].
A review of Integer Linear Programming that covers Benders Decomposition by Clautiaux and Ljubić [10].
Useful practical guidelines for implementing (Logic-based) Benders Decomposition (Section 2.7) [11].