Benders Cut¶

Cut¶

A linear Benders cut is a linear inequality (constraint) added to the master problem. This cut is generated to approximate the subproblem’s value function or exclude infeasible solutions. In BendersLib, all linear Benders cuts are implemented using the Cut class, which holds all the information needed to define a linear cut, which is a linear inequality of the following form.

\[\mathbf{c}^{\top} \mathbf{x} \le d\]

In the above inequality, \(\mathbf{x}\) represents the vector of variables (vars) involved in the cut, \(\mathbf{c}\) represents the vector of corresponding coefficients (coefs), and \(d\) is the right-hand side value (rhs). The sense of the inequality can be less than or equal to ('<='), greater than or equal to ('>='), or equal to ('=='). Correspondingly, the Cut class includes attributes to store these components.

vars: A list of variables involved in the cut.
coefs: The coefficients corresponding to the variables.
rhs: The right-hand side value of the inequality.
sense: The sense of the inequality (e.g., '<=', '>=', or '==').

Here is an example of how to create a Cut instance.

from benderslib import Cut, CST

# Create a cut: 2*x1 + 3*x2 <= 10
my_cut = Cut(
    vars=['x1', 'x2'],
    coefs=[2, 3],
    rhs=10,
    sense=CST.LE,  # or '<='
    ctype=CST.OPTIMALITY, # or CST.FEASIBILITY
    name="my_custom_cut"
)

Any linear Benders cut can be represented using an instance of the Cut class. The Benders cut instances are created and added to the master problem. The built-in cut types listed below are essentially syntactic sugar of Cut, providing convenient ways to define standard Benders cuts.

Built-in Benders Cuts

`ClassicalOC`	The optimality cut for Classical Benders Decomposition.
`ClassicalFC`	The feasibility cut for Classical Benders Decomposition.
`CombinatorialOC`	The optimality cut for Combinatorial Benders Decomposition.
`NoGoodFC`	The feasibility cut for Combinatorial Benders Decomposition.
`LShapedOC`	The optimality cut for L-shaped Method (single-cut & linear recourse).
`GeneralizedOC`	The optimality cut for Generalized Benders Decomposition.
`GeneralizedFC`	The feasibility cut for Generalized Benders Decomposition.
`GeneLShapedOC`	The optimality cut for L-shaped Method (single-cut & convex recourse).

* Note: “OC” stands for Optimality Cut, and “FC” stands for Feasibility Cut.

Cut Generator¶

In BendersLib, the generation of Benders cuts is managed by the CutGenerator class. While a Cut instance simply holds the data for a linear inequality, the CutGenerator contains the logic for creating that data. It acts as a factory for Cut objects, using information from the master problem and subproblem(s) to construct the appropriate cuts at each iteration. The key design aspects of the CutGenerator are as follows.

Separation of Concerns: It separates the cut generation logic from the cut data structure. The Cut is a simple data container, while the CutGenerator is responsible for the complex logic of calculating coefficients and right-hand side values.
Efficiency: A CutGenerator instance is initialized only once when the BendersSolver is instantiated. This allows the generator to pre-process and cache any information that remains constant throughout the solving process, such as the subproblem’s constraint matrix structure. This avoids redundant computations at each iteration, significantly improving performance.
Statefulness: Since the same CutGenerator instance is used across all iterations, it can maintain state. This is crucial for advanced strategies like cut strengthening, stabilization techniques, or other acceleration methods that require information aggregated over multiple iterations.
Lifecycle: The CutGenerator is instantiated when a BendersSolver class is created. During the BendersSolver.solve() loop, the CutGenerator.generate() method is called whenever a new cut is needed. The CutGenerator accesses information and solutions from the master and subproblems to create and return a list of Cut instances.

Here is an example of how cut generators ClassicalOCGen and ClassicalFCGen are passed to the ClassicalBenders solver.

from benderslib import ClassicalBenders, ClassicalOCGen, ClassicalFCGen, MasterProblem, SubProblem

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

solver = ClassicalBenders(
    master_problem, sub_problem, complicating_vars,
    optimality_cut=ClassicalOCGen,
    feasibility_cut=ClassicalFCGen
)
solver.solve()

Built-in Cut Generators

The classes listed below are all subclasses of CutGenerator. Each one implements a specific logic for generating cuts by overriding the CutGenerator.generate() method.

`ClassicalOCGen`	The optimality cut generator for Classical Benders Decomposition.
`ClassicalFCGen`	The feasibility cut generator for Classical Benders Decomposition.
`CombinatorialOCGen`	The optimality cut generator for Combinatorial Benders Decomposition.
`CombinatorialFCGen`	The feasibility cut generator for Combinatorial Benders Decomposition.
`LShapedOCGen`	The optimality cut generator for L-shaped Method (linear recourse).
`LShapedFCGen`	The feasibility cut generator for L-shaped Method.
`IntegerLShapedOCGen`	The optimality cut generator for Integer L-shaped Method.
`IntegerLShapedFCGen`	The feasibility cut generator for Integer L-shaped Method.
`GeneralizedOCGen`	The optimality cut generator for Generalized Benders Decomposition.
`GeneralizedFCGen`	The feasibility cut generator for Generalized Benders Decomposition.
`GeneLShapedOCGen`	The optimality cut generator for L-shaped Method (convex recourse).

* Note: “OC” stands for Optimality Cut, and “FC” stands for Feasibility Cut.

Caution

These classes are tailored for their respective Benders decomposition variants. Use them with caution in your own custom Benders decomposition unless you are certain that your implementation matches one of these variants.

Customization¶

BendersLib is designed to be highly customizable, allowing you to define your own Benders cuts and the logic for generating them. This is particularly useful when implementing advanced non-standard Benders decomposition methods.

Custom Benders Cut¶

While BendersLib’s built-in cut types are convenient, you can create your own custom cut class for clarity or to encapsulate specific logic. A custom cut class should inherit from OptimalityCut or FeasibilityCut. The primary purpose of a custom cut class is to structure the data required for a cut in a way that is meaningful and user-friendly for your specific problem.

Example

Here is an example of BendersLib’s built-in NoGoodFC cut, which excludes a specific binary solution from the master problem.

from benderslib import FeasibilityCut, CST

class NoGoodFC(FeasibilityCut):

    def __init__(self, bin_var_values: dict):
        # Retrieve variable values required for the cut
        var_zeros = [var for var, val in bin_var_values.items() if val <= 0.5]
        var_ones = [var for var, val in bin_var_values.items() if val > 0.5]

        vars = var_ones + var_zeros
        coefs = [1.0] * len(var_ones) + [-1.0] * len(var_zeros)
        rhs = len(var_ones) - 1

        # Call the parent constructor
        super().__init__(vars=vars, coefs=coefs, rhs=rhs, sense='<=', name="NoGoodFC")

More examples can be found in the source code of Benders Cuts.

Custom Cut Generator (class-based)¶

The core of customization lies in creating a custom cut generator, especially when implementing advanced decomposition methods based on Logic-based Benders Decomposition that require non-standard cuts. This requires obtaining the necessary information from the master and subproblems and computing the cut’s coefficients and right-hand side according to your specific logic. A class-based generator is the standard and most flexible approach in BendersLib.

To create and use one class-based cut generator, follow these steps.

Step 1. Define a class that inherits from CutGenerator.
Step 2. Implement the __init__ method to receive the master problem, subproblem(s), and parameters. This is the ideal place to cache data that does not change between iterations.
Step 3. Implement the CutGenerator.generate() method. This method is called in each iteration of the Benders algorithm and must return a list of Cut objects.
Step 4. Pass the custom cut generator class (not an instance) to the Benders solver when instantiating it.

Example

Here is an example of a custom cut generator that creates the NoGoodFC instances.

from benderslib import CutGenerator, BendersSolver, Cut

# Step 1: Define the custom cut generator class
class MyCutGen(CutGenerator):

    def __init__(self, master_problem, sub_problem, params):
        # Step 2: Initialization and caching
        # No data needs to be cached for this simple generator.
        # The __init__ can be left empty if no pre-processing is needed.
        super().__init__(master_problem, sub_problem, params)

    def generate(self) -> list[NoGoodFC]:
        # Step 3: Generate the cuts
        # Retrieve the values of the complicating variables from the master problem.
        # Create the custom cut
        infeasible_solution = self.master_problem.get_var_values(self.complicating_vars)
        cut = NoGoodFC(infeasible_solution)
        # cut = Cut(...)  # Alternatively, create a Cut instance directly.
        return [cut]  # Return a list of cuts, even if it's just one.

# Step 4: Use the custom cut generator in the Benders solver
solver = BendersSolver(
    master_problem,
    sub_problem,
    complicating_vars,
    feasibility_cut=MyCutGen,  # Pass the custom cut generator class
)
solver.solve()

More examples can be found in the source code of Cut Generators.

Custom Cut Generator (function-based)¶

For simpler cases, you may not need a full class for your cut generation logic. BendersLib also supports using a simple function as a cut generator. This can make the code more concise if you don’t need to cache data or maintain state between iterations. A generator function must accept three arguments: master_problem, sub_problem, and complicating_vars. It should return a list of one or more cut objects. Here is an example of a function-based generator to generate NoGoodFC. It is equivalent to the earlier class-based example.

from benderslib import Cut, CST, BendersSolver

def simple_fc_generator(master_problem, sub_problem, complicating_vars) -> list[Cut]:
    # Retrieve the values of the complicating variables from the master problem.
    bin_var_values = master_problem.get_var_values(complicating_vars)

    # Create the cut using NoGoodFC
    cut = NoGoodFC(bin_var_values)
    return [cut]

# To use it, simply pass the function to the solver.
solver = BendersSolver(
    master_problem,
    sub_problem,
    complicating_vars,
    feasibility_cut=simple_fc_generator,  # Pass the custom cut generator function
)
solver.solve()

Example

Integer L-shaped Method (IIS), Logic-Based Benders Decomposition, Facility Location (Gurobi)

Attributes & Methods¶

Let BendersCut and BendersCutGen be generic names for Benders cut classes and cut generator classes (e.g., ClassicalOCGen), respectively. The diagram below illustrates the inheritance and usage relationships among the relevant classes. Any BendersCut inherits from Cut, OptimalityCut, or FeasibilityCut, and is generated by a BendersCutGen that inherits from CutGenerator. The BendersCutGen uses information from SubProblem (or SubProblems, LogicBasedSubProblem) and MasterProblem instances to generate the cuts, and the generated BendersCut is added back to the MasterProblem.

        flowchart LR
    BendersCutGen -- generates --> BendersCut
    BendersCutGen -- inherits --> CutGenerator

    BendersCut -- is added to --> MasterProblem
    OptimalityCut -- inherits --> Cut
    FeasibilityCut -- inherits --> Cut
    BendersCut -. inherits .-> OptimalityCut
    BendersCut -. inherits .-> FeasibilityCut
    BendersCut -. inherits .-> Cut

    BendersCutGen -- uses --> SubProblem
    BendersCutGen -- uses --> MasterProblem

style MasterProblem fill:#f2f2f2,stroke:#333,stroke-width:1px
style SubProblem fill:#f2f2f2,stroke:#333,stroke-width:1px
style BendersCutGen fill:white,stroke:#333,stroke-width:1px
style BendersCut fill:white,stroke:#333,stroke-width:1px

Cut and Cut Generator Inheritance Diagram¶

*Note: Dashed arrows indicate optional relationships, from which exactly one must be selected for each usage.

Below are the attributes and methods of the Cut and CutGenerator classes. OptimalityCut and FeasibilityCut inherit from Cut, and share the same attributes and methods. Please refer to Benders Cuts and Cut Generators for the attributes and methods of specific implementations.

Cut - Attributes

`vars`	The list of variable names involved in the cut.
`coefs`	The list of coefficients corresponding to the variables in the cut.
`rhs`	The right-hand side value of the cut.
`sense`	The sense of the cut.
`ctype`	The indicator of the cut type.
`name`	The name for the cut.

Cut - Methods

There is no public method.

CutGenerator - Attributes

`master_problem`	The master problem instance.
`sub_problem`	The subproblem instance.
`complicating_vars`	A list of names of the complicating variables.
`params`	The parameters that can be set by the user (see `BendersParams`).

CutGenerator - Methods

generate

Generate a list of Benders cuts based on the current state of the master and subproblem(s) (required to be implemented).