Benders Methods¶

Create a Benders Decomposition Instance¶

To create a Benders decomposition instance, you need to provide a master problem, a subproblem, and a list of complicating variable names. BendersLib will then build a Benders decomposition framework to your problem.

from benderslib import ClassicalBenders, MasterProblem, SubProblem

# Assume master_problem and sub_problem are already defined
master_problem: MasterProblem = ...
sub_problem: SubProblem = ...
complicating_vars: list[str] = ...

# Create a Benders Decomposition instance
benders_solver = ClassicalBenders(
    master_problem=master_problem,
    sub_problem=sub_problem,
    complicating_vars=complicating_vars
)

Alternatively, you can create a Benders decomposition instance directly from your models using the from_models() class method. This method is a convenient way to instantiate a Benders solver without manually creating MasterProblem and SubProblem objects.

from benderslib import ClassicalBenders
from benderslib.solvers import Gurobi

# Assume master_model and sub_model are already defined
master_model = ...
sub_model = ...
complicating_vars: list[str] = ...

# Create a Benders Decomposition instance from models
benders_solver = ClassicalBenders.from_models(
    master_model=master_model,
    master_solver=Gurobi,
    sub_model=sub_model,
    sub_solver=Gurobi,
    complicating_vars=complicating_vars
)

BendersLib offers several built-in Benders decomposition methods, each designed for specific problem structures. These methods are subclasses of BendersSolver and come pre-configured with appropriate cut generators. Each of the classes (except LogicBasedBenders) is a ready-to-use implementation of a Benders decomposition variant.

Built-in Benders Decomposition Methods

`ClassicalBenders`	An implementation of Classical Benders Decomposition.
`CombinatorialBenders`	An implementation of Combinatorial Benders Decomposition.
`LShaped`	An implementation of L-shaped Method (linear recourse).
`IntegerLShaped`	An implementation of Integer L-shaped Method.
`LogicBasedBenders`	An implementation of Logic-based Benders Decomposition.
`GeneralizedBenders`	An implementation of Generalized Benders Decomposition.
`GeneLShaped`	An implementation of L-shaped Method (convex recourse).

Options for Benders Decomposition¶

These options are set after creating a Benders Decomposition instance, but before calling the BendersSolver.solve() method. Please refer to BendersParams for the available options to customize the behavior of BendersLib’s Benders Decomposition methods.

from benderslib import ClassicalBenders, BendersParams

# Create Benders Decomposition instance
benders_solver = ClassicalBenders(master_problem, sub_problem, complicating_vars)

# Customize Benders parameters
benders_solver.params.time_limit = 600  # Set time limit to 600 seconds

Alternatively, you can pass a BendersParams instance as an argument when creating the Benders Decomposition instance.

from benderslib import ClassicalBenders, BendersParams

# Customize Benders parameters
params = BendersParams()
params.time_limit = 600  # Set time limit to 600 seconds

# Create Benders Decomposition instance with custom parameters
benders_solver = ClassicalBenders(
    master_problem, sub_problem, complicating_vars,
    params=params
)

Solve the Benders Decomposition Instance¶

After creating and customizing a Benders Decomposition instance, you can solve it using the BendersSolver.solve() method.

# Solve the Benders Decomposition instance
result = benders_solver.solve()

The output in the console will display the progress of the Benders Decomposition algorithm, including iteration details and convergence information.

====================================================================================
BendersLib (v0.5.1, Apache-2.0, https://benders.dev) (C) 2021-2026 Peng-Hui Guo
------------------------------------------------------------------------------------
Benders Decomposition:
 - Method:                  ClassicalBenders
 - Complicating Var. No.:   1 [Integer: 1, Binary: 0, Continuous: 0]
 - Optimality Cut:          ClassicalOCGen
 - Feasibility Cut:         ClassicalFCGen
Master Problem:
 - Variable No.:            2 [Integer: 1, Binary: 0]
 - Constraint No.:          0
 - Solver:                  Gurobi
Sub Problem:
 - Variable No.:            1 [Integer: 0, Binary: 0]
 - Constraint No.:          2
 - Solver:                  Gurobi
Benders Parameters:
 - All default
------------------------------------------------------------------------------------
       Iter.,           LB,           UB,         Obj.,       Gap(%),   Runtime(s)
------------------------------------------------------------------------------------
           1,         0.00,        60.00,        60.00,       100.00,         0.00
------------------------------------------------------------------------------------
Benders Result:
  - Status:                  OPTIMAL
  - Incumbent:               45.0000
  - Bound:                   45.0000
  - Gap (abs.):              0.0000
  - Gap (rel.):              0.00%
  - Solutions No.:           2
  - Iteration No.:           2
  - Cuts No.:                1 [Optimality: 1, Feasibility: 0]
  - Solve Time (sec.):       0.01 [Master: 0.01, Sub: 0.00]
====================================================================================

The console output provides a summary of the Benders decomposition process, starting with a header displaying library and copyright information; followed by problem information detailing the decomposition setup, including the method, complicating variables, and cut generators; an iteration log tracking the lower and upper bounds, objective value, and runtime; and a final results section summarizing the outcome with the solution status, incumbent value, and performance metrics.

Access Additional Statistics¶

To access additional statistics after solving, you can use the BendersSolver.result attribute, which contains various information about the solution process. This attribute is an instance of the BendersResult class.

# Access Benders result statistics
print(f"Status: {benders_solver.result.status}")
print(f"Objective: {benders_solver.result.obj}")
print(f"Lower Bound: {benders_solver.result.lb}")
print(f"Upper Bound: {benders_solver.result.ub}")
print(f"Gap (abs.): {benders_solver.result.gap_abs}")
print(f"Gap (rel.): {benders_solver.result.gap:.2%}")
print(f"Number of Solutions: {benders_solver.result.n_sol}")
print(f"Number of Iterations: {benders_solver.result.n_iter}")
print(f"Number of Cuts: {benders_solver.result.n_cuts} (Opt: {benders_solver.result.n_opt_cuts}, Feas: {benders_solver.result.n_feas_cuts})")
print(f"Solve Time (sec.): {benders_solver.result.runtime}")
print(f"Solution: {benders_solver.result.solution}")

Automated Decomposition¶

BendersLib provides an automated decomposition feature through the AnnotatedBenders class. This allows you to decompose a problem by simply providing the original model and specifying the complicating/master variables. BendersLib will then automatically create the master problem and subproblem. Here’s how to use the automated decomposition feature.

from benderslib import AnnotatedBenders, ClassicalBenders
from benderslib.solvers import Gurobi
from gurobipy import Model, GRB

# Define the original problem
def make_original_problem():
    model = Model("Original")
    y = model.addVar(name="y", lb=0, ub=40, vtype=GRB.INTEGER)
    z = model.addVar(name="z", lb=0, ub=40, vtype=GRB.CONTINUOUS)
    model.addConstr(y + z <= 50)
    model.addConstr(2 * y <= 20)
    model.addConstr(2 * y + z >= 10)
    model.setObjective(2 * y + 3 * z, sense=GRB.MINIMIZE)
    model.update()
    complicating_vars = [y.VarName]
    return model, complicating_vars

# Create an AnnotatedBenders instance
original_problem, complicating_vars = make_original_problem()
benders_solver = AnnotatedBenders(
    original_problem=original_problem,
    solver=Gurobi,
    benders=ClassicalBenders,
    complicating_vars=complicating_vars,
)

# Solve the problem
benders_solver.solve()
print(f"Objective: {benders_solver.result.obj}")
print(f"Solution: {benders_solver.result.solution}")

In this example, AnnotatedBenders takes the complete optimization model, identifies the master-only and subproblem-only variables and constraints based on the provided complicating_vars, and then constructs the master problem and subproblem. Finally, it uses the specified Benders method (ClassicalBenders in this case) to solve the decomposed problem.

Caution

You are responsible for ensuring the type of the master problem and subproblem are compatible with the chosen Benders Decomposition method, based on the given complicating variables For example, if your subproblem contains integer variables, and you choose ClassicalBenders, the algorithm will not function correctly since ClassicalBenders assumes a Linear Programming subproblem.

Example

Automated Decomposition, Annotated Benders Decomposition, Retrieve master and sub problems, Combinatorial Benders Decomposition

Customization¶

BendersLib is highly customizable, allowing you to tailor the decomposition process to your specific needs. You can create custom cut (generators) and define your own subproblem logic. A common use case for customization is Logic-based Benders Decomposition where Benders cuts and subproblem solver are problem-specific. Here is a code snippet showing how to set up a LogicBasedBenders instance.

from benderslib import LogicBasedBenders, MasterProblem, LogicBasedSubProblem, CutGenerator
from benderslib.solvers import Gurobi

# Define master problem model
master_model = ...  # Define your master problem model here
mp = MasterProblem(Gurobi(master_model))

# Define a custom logic-based subproblem
class MyLogicBasedSubProblem(LogicBasedSubProblem):
    def solve():
        # Implement the logic to solve the subproblem given the complicating variable values
        self.status = ...
        self.obj = ...
        self.var_values = ...

sp = MyLogicBasedSubProblem()

# Define a custom optimality cut generator
class MyOptimalityCutGenerator(CutGenerator):
    def generate_cut(self, master_solution, subproblem):
        cuts = []
        # Implement the logic to generate an optimality cut
        cut = ...
        cuts.append(cut)
        return cuts

# Define complicating variables
complicating_vars = ['x1', 'x2', 'x3']

# Initialize and solve
BD = LogicBasedBenders(mp, sp, complicating_vars, optimality_cut=MyOptimalityCutGenerator)
BD.solve()

Attributes & Methods¶

The class BendersSolver is the base class for all Benders Decomposition implementations. Specific implementations, e.g., ClassicalBenders, inherit from this class. The diagram below illustrates the main inheritance and composition relationships among the relevant classes. A BendersSolver instance is composed of MasterProblem, SubProblem (or SubProblems, LogicBasedSubProblem), and CutGenerator instances to handle their respective functionalities.

        flowchart LR
    BendersSolver -- has --> CutGenerator
    BendersSolver -- has --> MasterProblem
    BendersSolver -- has --> SubProblem

    CutGenerator -- generates --> Cut
    Cut -- is added to --> MasterProblem

    CutGenerator -- uses --> SubProblem
    CutGenerator -- uses --> MasterProblem

    style MasterProblem fill:#f2f2f2,stroke:#333,stroke-width:1px
    style SubProblem fill:#f2f2f2,stroke:#333,stroke-width:1px
    style CutGenerator fill:#f2f2f2,stroke:#333,stroke-width:1px
    style Cut fill:#f2f2f2,stroke:#333,stroke-width:1px

Benders Solver Inheritance Diagram¶

Below are the attributes and methods of the BendersSolver class. Please refer to Benders Methods for the attributes and methods of specific implementations.

BendersSolver - Attributes

`master_problem`	An instance of `MasterProblem` representing the master problem.
`sub_problem`	An instance of `SubProblem` or `SubProblems` representing the subproblem(s).
`complicating_vars`	A list of names of the complicating variables.
`optimality_cut`	An instance of `CutGenerator` for generating optimality cuts.
`feasibility_cut`	An instance of `CutGenerator` for generating feasibility cuts.
`params`	The parameters that can be set by the user (see `BendersParams`).
`result`	An instance of `BendersResult` that stores the results and statistics.

BendersSolver - Methods

`solve`	Solve the problem using Benders decomposition.
`from_models`	Class method to create a `BendersSolver` instance directly from solver models.