Benders Methods

class ClassicalBenders(master_problem: ~benderslib.core.MasterProblem, sub_problem: ~benderslib.core.SubProblem, complicating_vars: list[str], optimality_cut=<class 'benderslib.cuts.generators.ClassicalOCGen'>, feasibility_cut=<class 'benderslib.cuts.generators.ClassicalFCGen'>, params: ~benderslib.params.BendersParams | None = None)[source]

Bases: BendersSolver

An implementation of Classical Benders Decomposition.

It builds a Benders decomposition framework using the provided master problem, subproblem, and complicating variables. The optimality cut is defined by ClassicalOC and generated by ClassicalOCGen; the feasibility cut is defined by ClassicalFC and generated by ClassicalFCGen.

Caution

The class ClassicalBenders requires the subproblem be pure LP.

Parameters:

  • master_problem (MasterProblem) – An instance of MasterProblem representing the master problem.

  • sub_problem (SubProblem) – An instance of SubProblem representing the subproblem.

  • complicating_vars (list[str]) – A list of names of the complicating variables.

  • params (BendersParams, optional) – An instance of BendersParams containing parameters for the Benders decomposition process. If not provided, default parameters will be used.

Example

from benderslib import ClassicalBenders, MasterProblem, SubProblem
from benderslib.solvers import Gurobi

# Define master and subproblem models
master_model = ...  # Define your master problem model here
sub_model = ...     # Define your subproblem model here

# Initialize master and subproblem
mp = MasterProblem(Gurobi(master_model))
sp = SubProblem(Gurobi(sub_model))

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

# Initialize and solve
BD = ClassicalBenders(mp, sp, complicating_vars)
BD.solve()
classmethod from_models(master_model, master_solver, sub_model, sub_solver, complicating_vars, optimality_cut=<class 'benderslib.cuts.generators.ClassicalOCGen'>, feasibility_cut=<class 'benderslib.cuts.generators.ClassicalFCGen'>, prob=None, params: BendersParams | None = None)[source]

Class method to create a BendersSolver instance directly from solver models.

Parameters:

  • master_model – Solver model instance for the master problem (e.g., gurobipy.Model).

  • master_solver (Type[SolverBase]) – An abstract class that inherits from SolverBase to be used as the solver backend for the master problem.

  • sub_model – Solver model instance for the subproblem (e.g., gurobipy.Model).

  • sub_solver (Type[SolverBase]) – An abstract class that inherits from SolverBase to be used as the solver backend for the subproblem.

  • complicating_vars (list[str]) – A list of names of the complicating variables.

  • optimality_cut (Type[CutGenerator], optional) – An abstract class that inherits from CutGenerator to be used for generating optimality cuts. It also accepts a function with signature func(master_problem, sub_problem) -> list[OptimalityCut]. If None, no optimality cuts will be added.

  • feasibility_cut (Type[CutGenerator], optional) – An abstract class that inherits from CutGenerator to be used for generating feasibility cuts. It also accepts a function with signature func(master_problem, sub_problem) -> list[FeasibilityCut]. If None, no feasibility cuts will be added.

  • prob (list[float], optional) – A list of probabilities (or weights) for each subproblem when using multiple subproblems (L-shaped method).

  • params (BendersParams, optional) – The parameters that can be set by the user (see BendersParams). If not provided, default parameters will be used.

Example

from benderslib import BendersSolver
from benderslib.solvers import Gurobi
from gurobipy import Model

# Create master and subproblem models using Gurobi
master_model = Model()
# ... (define master problem variables, constraints, and objective)
sub_model = Model()
# ... (define subproblem variables, constraints, and objective)
complicating_vars = ['x1', 'x2']

# Create BendersSolver instance from models
benders_solver = BendersSolver.from_models(
    master_model = master_model,
    master_solver = Gurobi,
    sub_model = sub_model,
    sub_solver = Gurobi,
    complicating_vars = complicating_vars
)
bnc_solve()

Solve the problem using Branch-and-check method.

branch-and-check, or branch-and-Benders-cut, is a modern implementation of the Benders decomposition method that integrates the cut generation process into the branch-and-bound algorithm of the master problem solver. Instead of solving the master problem to optimality at each iteration, it checks the feasibility and optimality of the current solution at each node of the branch-and-bound tree and adds cuts as needed.

The Branch-and-check method is especially efficient when the subproblem is relatively easy to solve (than the master problem) and the number of cuts needed is large, as it avoids solving the master problem multiple times. However, it requires the master problem solver to support callback functions for adding cuts during the branch-and-bound process, which is supported by only a subset of solver interfaces.

When running Branch-and-check, BendersLib does not check whether the cut generated has been already added to the master problem, as another node may encounter the same solution and generate the same cut, which is not necessarily redundant in Branch-and-check. This differs from running the traditional Benders method using solve(), which warns users about duplicate cuts and skips adding them to the master problem.

The definition of the lower bound (and the gap) in Branch-and-check is different from the traditional Benders decomposition, as the master problem is not necessarily solved to optimality when cuts are added. Therefore, the master problem objective value at the current node may not be a valid lower bound for the original problem. In Branch-and-check, the lower bound is obtained from the best bound of the master problem at the current node. Therefore, users should be cautious when interpreting the results and statistics in Branch-and-check, and keep in mind that it is not directly comparable to the traditional Benders decomposition. The latter is usually stronger.

The runtime_master also differs from the traditional Benders decomposition, as there is not a clear separation that can be used to record the time of solving the master problem. In Branch-and-check, runtime_master simply equals the total runtime (runtime) minus the time spent on solving the subproblem (runtime_sub).

This method can also be used by setting use_bnc to True and calling solve(), which will internally call this method.

Caution

The method bnc_solve() is incompatible with Benders decomposition instances that have a purely continuous master problem. This is because the Branch-and-check method generates cuts on nodes of the branch-and-bound tree, which does not exist for Linear Programming problems.

Example

BD = BendersSolver(...)

BD.bnc_solve()
# or equivalently
BD.params.use_bnc = True
BD.solve()
register(callback: CallbackBase | Callable | Type[CallbackBase]) → None

Register a user-defined callback to be called during the Benders solving process.

Users can define custom callbacks by inheriting from CallbackBase and overriding the desired event methods. Each method receives a BendersContext object containing information about the current state of the Benders decomposition process. Alternatively, users can define standalone functions with names matching the methods in CallbackBase to serve as lightweight callbacks.

Parameters:

callback (CallbackBase | Callable | Type[CallbackBase]) – A callback instance (or class) inherited from CallbackBase or a function with signature func(context: BendersContext) -> CST.PROCEED | CST.TERMINATE | None.

Example

from benderslib.callback import CallbackBase, BendersContext

# Class-based callback
class MyCallback(CallbackBase):

    def on_benders_start(self, context: BendersContext):
        print("Benders process started!")

# Function-based callback
def on_benders_end(self, context: BendersContext):
    print("Benders process finished!")

BD = BendersSolver(...)
BD.register(MyCallback())
BD.register(on_benders_end)
save(filename: str) → None

Save the statistics of the Benders decomposition process to a JSON file.

Parameters:

filename (str) – Path to the JSON file where the result will be saved.

solve() → None

Solve the problem using Benders decomposition.

This method implements the main Benders decomposition algorithm, iteratively solving the master and subproblems, adding cuts, and updating the results until convergence or stopping criteria are met.

After calling this method, the results and statistics of the Benders decomposition process can be accessed through the BendersSolver.result attribute, which is an instance of BendersResult.

class CombinatorialBenders(master_problem: ~benderslib.core.MasterProblem, sub_problem: ~benderslib.core.SubProblem, complicating_vars: list[str], optimality_cut=<class 'benderslib.cuts.generators.CombinatorialOCGen'>, feasibility_cut=<class 'benderslib.cuts.generators.CombinatorialFCGen'>, params: ~benderslib.params.BendersParams | None = None)[source]

Bases: BendersSolver

An implementation of Combinatorial Benders Decomposition.

It builds a Benders decomposition framework using the provided master problem, subproblem, and complicating variables. The optimality cut is defined by CombinatorialOC and generated by CombinatorialOCGen; the feasibility cut is defined by NoGoodFC and generated by CombinatorialFCGen.

Caution

The class CombinatorialBenders requires the complicating variables be pure binary (0-1).

Parameters:

  • master_problem (MasterProblem) – An instance of MasterProblem representing the master problem.

  • sub_problem (SubProblem) – An instance of SubProblem representing the subproblem.

  • complicating_vars (list[str]) – A list of names of the complicating variables.

  • params (BendersParams, optional) – An instance of BendersParams containing parameters for the Benders decomposition process. If not provided, default parameters will be used.

Example

from benderslib import CombinatorialBenders, MasterProblem, SubProblem
from benderslib.solvers import Gurobi

# Define master and subproblem models
master_model = ...  # Define your master problem model here
sub_model = ...     # Define your subproblem model here

# Initialize master and subproblem
mp = MasterProblem(Gurobi(master_model))
sp = SubProblem(Gurobi(sub_model))

# Define complicating variables (must be binary)
complicating_vars = ['x1', 'x2', 'x3']

# Initialize and solve
BD = CombinatorialBenders(mp, sp, complicating_vars)
BD.solve()
classmethod from_models(master_model, master_solver, sub_model, sub_solver, complicating_vars, optimality_cut=<class 'benderslib.cuts.generators.CombinatorialOCGen'>, feasibility_cut=<class 'benderslib.cuts.generators.CombinatorialFCGen'>, prob=None, params: BendersParams | None = None)[source]

Class method to create a BendersSolver instance directly from solver models.

Parameters:

  • master_model – Solver model instance for the master problem (e.g., gurobipy.Model).

  • master_solver (Type[SolverBase]) – An abstract class that inherits from SolverBase to be used as the solver backend for the master problem.

  • sub_model – Solver model instance for the subproblem (e.g., gurobipy.Model).

  • sub_solver (Type[SolverBase]) – An abstract class that inherits from SolverBase to be used as the solver backend for the subproblem.

  • complicating_vars (list[str]) – A list of names of the complicating variables.

  • optimality_cut (Type[CutGenerator], optional) – An abstract class that inherits from CutGenerator to be used for generating optimality cuts. It also accepts a function with signature func(master_problem, sub_problem) -> list[OptimalityCut]. If None, no optimality cuts will be added.

  • feasibility_cut (Type[CutGenerator], optional) – An abstract class that inherits from CutGenerator to be used for generating feasibility cuts. It also accepts a function with signature func(master_problem, sub_problem) -> list[FeasibilityCut]. If None, no feasibility cuts will be added.

  • prob (list[float], optional) – A list of probabilities (or weights) for each subproblem when using multiple subproblems (L-shaped method).

  • params (BendersParams, optional) – The parameters that can be set by the user (see BendersParams). If not provided, default parameters will be used.

Example

from benderslib import BendersSolver
from benderslib.solvers import Gurobi
from gurobipy import Model

# Create master and subproblem models using Gurobi
master_model = Model()
# ... (define master problem variables, constraints, and objective)
sub_model = Model()
# ... (define subproblem variables, constraints, and objective)
complicating_vars = ['x1', 'x2']

# Create BendersSolver instance from models
benders_solver = BendersSolver.from_models(
    master_model = master_model,
    master_solver = Gurobi,
    sub_model = sub_model,
    sub_solver = Gurobi,
    complicating_vars = complicating_vars
)
bnc_solve()

Solve the problem using Branch-and-check method.

branch-and-check, or branch-and-Benders-cut, is a modern implementation of the Benders decomposition method that integrates the cut generation process into the branch-and-bound algorithm of the master problem solver. Instead of solving the master problem to optimality at each iteration, it checks the feasibility and optimality of the current solution at each node of the branch-and-bound tree and adds cuts as needed.

The Branch-and-check method is especially efficient when the subproblem is relatively easy to solve (than the master problem) and the number of cuts needed is large, as it avoids solving the master problem multiple times. However, it requires the master problem solver to support callback functions for adding cuts during the branch-and-bound process, which is supported by only a subset of solver interfaces.

When running Branch-and-check, BendersLib does not check whether the cut generated has been already added to the master problem, as another node may encounter the same solution and generate the same cut, which is not necessarily redundant in Branch-and-check. This differs from running the traditional Benders method using solve(), which warns users about duplicate cuts and skips adding them to the master problem.

The definition of the lower bound (and the gap) in Branch-and-check is different from the traditional Benders decomposition, as the master problem is not necessarily solved to optimality when cuts are added. Therefore, the master problem objective value at the current node may not be a valid lower bound for the original problem. In Branch-and-check, the lower bound is obtained from the best bound of the master problem at the current node. Therefore, users should be cautious when interpreting the results and statistics in Branch-and-check, and keep in mind that it is not directly comparable to the traditional Benders decomposition. The latter is usually stronger.

The runtime_master also differs from the traditional Benders decomposition, as there is not a clear separation that can be used to record the time of solving the master problem. In Branch-and-check, runtime_master simply equals the total runtime (runtime) minus the time spent on solving the subproblem (runtime_sub).

This method can also be used by setting use_bnc to True and calling solve(), which will internally call this method.

Caution

The method bnc_solve() is incompatible with Benders decomposition instances that have a purely continuous master problem. This is because the Branch-and-check method generates cuts on nodes of the branch-and-bound tree, which does not exist for Linear Programming problems.

Example

BD = BendersSolver(...)

BD.bnc_solve()
# or equivalently
BD.params.use_bnc = True
BD.solve()
register(callback: CallbackBase | Callable | Type[CallbackBase]) → None

Register a user-defined callback to be called during the Benders solving process.

Users can define custom callbacks by inheriting from CallbackBase and overriding the desired event methods. Each method receives a BendersContext object containing information about the current state of the Benders decomposition process. Alternatively, users can define standalone functions with names matching the methods in CallbackBase to serve as lightweight callbacks.

Parameters:

callback (CallbackBase | Callable | Type[CallbackBase]) – A callback instance (or class) inherited from CallbackBase or a function with signature func(context: BendersContext) -> CST.PROCEED | CST.TERMINATE | None.

Example

from benderslib.callback import CallbackBase, BendersContext

# Class-based callback
class MyCallback(CallbackBase):

    def on_benders_start(self, context: BendersContext):
        print("Benders process started!")

# Function-based callback
def on_benders_end(self, context: BendersContext):
    print("Benders process finished!")

BD = BendersSolver(...)
BD.register(MyCallback())
BD.register(on_benders_end)
save(filename: str) → None

Save the statistics of the Benders decomposition process to a JSON file.

Parameters:

filename (str) – Path to the JSON file where the result will be saved.

solve() → None

Solve the problem using Benders decomposition.

This method implements the main Benders decomposition algorithm, iteratively solving the master and subproblems, adding cuts, and updating the results until convergence or stopping criteria are met.

After calling this method, the results and statistics of the Benders decomposition process can be accessed through the BendersSolver.result attribute, which is an instance of BendersResult.

class GeneralizedBenders(master_problem: ~benderslib.core.MasterProblem, sub_problem: ~benderslib.core.SubProblem, complicating_vars: list[str], optimality_cut=<class 'benderslib.cuts.generators.GeneralizedOCGen'>, feasibility_cut=<class 'benderslib.cuts.generators.GeneralizedFCGen'>, params: ~benderslib.params.BendersParams | None = None)[source]

Bases: BendersSolver

An implementation of Generalized Benders Decomposition.

It builds a Benders decomposition framework using the provided master problem, subproblem, and complicating variables. The optimality cut is defined by GeneralizedOC and generated by GeneralizedOCGen; the feasibility cut is defined by GeneralizedFC and generated by GeneralizedFCGen.

Caution

  • Currently, the class GeneralizedBenders requires the problem meets certain conditions.

    • Original Problem: The original problem must be linearly separable, i.e., the objective function can be written as \(f(x,y) = f_x(x) + f_y(y)\), and the constraints can be written as \(g(x,y) = g_x(x) + g_y(y) \leq 0\).

    • Master Problem: Constraints must be linear in terms of the complicating variables (necessary for linear Benders cuts). There are no restrictions on the objective function or decision variable types from BendersLib’s perspective.

    • Subproblem: To derive optimality cuts, the subproblem must be a convex optimization problem (with decision variables being continuous); to derive feasibility cuts, the subproblem constraints must form a linear system with decision variables being continuous. When you need both types of cuts, the subproblem must satisfy both conditions.

  • There are also limitations from solver backends regarding the types of problems that can be handled, please refer to the documentation of each solver for details.

Parameters:

  • master_problem (MasterProblem) – An instance of MasterProblem representing the master problem.

  • sub_problem (SubProblem) – An instance of SubProblem representing the subproblem.

  • complicating_vars (list[str]) – A list of names of the complicating variables.

  • params (BendersParams, optional) – An instance of BendersParams containing parameters for the Benders decomposition process. If not provided, default parameters will be used.

Example

from benderslib import GeneralizedBenders, MasterProblem, SubProblem
from benderslib.solvers import Gurobi

# Define master and subproblem models
master_model = ...  # Define your linear master problem model here
sub_model = ...     # Define your convex nonlinear subproblem model here

# Initialize master and subproblem
mp = MasterProblem(Gurobi(master_model))
sp = SubProblem(Gurobi(sub_model))

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

# Initialize and solve
BD = GeneralizedBenders(mp, sp, complicating_vars)
BD.solve()
classmethod from_models(master_model, master_solver, sub_model, sub_solver, complicating_vars, optimality_cut=<class 'benderslib.cuts.generators.GeneralizedOCGen'>, feasibility_cut=<class 'benderslib.cuts.generators.GeneralizedFCGen'>, prob=None, params: BendersParams | None = None)[source]

Class method to create a BendersSolver instance directly from solver models.

Parameters:

  • master_model – Solver model instance for the master problem (e.g., gurobipy.Model).

  • master_solver (Type[SolverBase]) – An abstract class that inherits from SolverBase to be used as the solver backend for the master problem.

  • sub_model – Solver model instance for the subproblem (e.g., gurobipy.Model).

  • sub_solver (Type[SolverBase]) – An abstract class that inherits from SolverBase to be used as the solver backend for the subproblem.

  • complicating_vars (list[str]) – A list of names of the complicating variables.

  • optimality_cut (Type[CutGenerator], optional) – An abstract class that inherits from CutGenerator to be used for generating optimality cuts. It also accepts a function with signature func(master_problem, sub_problem) -> list[OptimalityCut]. If None, no optimality cuts will be added.

  • feasibility_cut (Type[CutGenerator], optional) – An abstract class that inherits from CutGenerator to be used for generating feasibility cuts. It also accepts a function with signature func(master_problem, sub_problem) -> list[FeasibilityCut]. If None, no feasibility cuts will be added.

  • prob (list[float], optional) – A list of probabilities (or weights) for each subproblem when using multiple subproblems (L-shaped method).

  • params (BendersParams, optional) – The parameters that can be set by the user (see BendersParams). If not provided, default parameters will be used.

Example

from benderslib import BendersSolver
from benderslib.solvers import Gurobi
from gurobipy import Model

# Create master and subproblem models using Gurobi
master_model = Model()
# ... (define master problem variables, constraints, and objective)
sub_model = Model()
# ... (define subproblem variables, constraints, and objective)
complicating_vars = ['x1', 'x2']

# Create BendersSolver instance from models
benders_solver = BendersSolver.from_models(
    master_model = master_model,
    master_solver = Gurobi,
    sub_model = sub_model,
    sub_solver = Gurobi,
    complicating_vars = complicating_vars
)
bnc_solve()

Solve the problem using Branch-and-check method.

branch-and-check, or branch-and-Benders-cut, is a modern implementation of the Benders decomposition method that integrates the cut generation process into the branch-and-bound algorithm of the master problem solver. Instead of solving the master problem to optimality at each iteration, it checks the feasibility and optimality of the current solution at each node of the branch-and-bound tree and adds cuts as needed.

The Branch-and-check method is especially efficient when the subproblem is relatively easy to solve (than the master problem) and the number of cuts needed is large, as it avoids solving the master problem multiple times. However, it requires the master problem solver to support callback functions for adding cuts during the branch-and-bound process, which is supported by only a subset of solver interfaces.

When running Branch-and-check, BendersLib does not check whether the cut generated has been already added to the master problem, as another node may encounter the same solution and generate the same cut, which is not necessarily redundant in Branch-and-check. This differs from running the traditional Benders method using solve(), which warns users about duplicate cuts and skips adding them to the master problem.

The definition of the lower bound (and the gap) in Branch-and-check is different from the traditional Benders decomposition, as the master problem is not necessarily solved to optimality when cuts are added. Therefore, the master problem objective value at the current node may not be a valid lower bound for the original problem. In Branch-and-check, the lower bound is obtained from the best bound of the master problem at the current node. Therefore, users should be cautious when interpreting the results and statistics in Branch-and-check, and keep in mind that it is not directly comparable to the traditional Benders decomposition. The latter is usually stronger.

The runtime_master also differs from the traditional Benders decomposition, as there is not a clear separation that can be used to record the time of solving the master problem. In Branch-and-check, runtime_master simply equals the total runtime (runtime) minus the time spent on solving the subproblem (runtime_sub).

This method can also be used by setting use_bnc to True and calling solve(), which will internally call this method.

Caution

The method bnc_solve() is incompatible with Benders decomposition instances that have a purely continuous master problem. This is because the Branch-and-check method generates cuts on nodes of the branch-and-bound tree, which does not exist for Linear Programming problems.

Example

BD = BendersSolver(...)

BD.bnc_solve()
# or equivalently
BD.params.use_bnc = True
BD.solve()
register(callback: CallbackBase | Callable | Type[CallbackBase]) → None

Register a user-defined callback to be called during the Benders solving process.

Users can define custom callbacks by inheriting from CallbackBase and overriding the desired event methods. Each method receives a BendersContext object containing information about the current state of the Benders decomposition process. Alternatively, users can define standalone functions with names matching the methods in CallbackBase to serve as lightweight callbacks.

Parameters:

callback (CallbackBase | Callable | Type[CallbackBase]) – A callback instance (or class) inherited from CallbackBase or a function with signature func(context: BendersContext) -> CST.PROCEED | CST.TERMINATE | None.

Example

from benderslib.callback import CallbackBase, BendersContext

# Class-based callback
class MyCallback(CallbackBase):

    def on_benders_start(self, context: BendersContext):
        print("Benders process started!")

# Function-based callback
def on_benders_end(self, context: BendersContext):
    print("Benders process finished!")

BD = BendersSolver(...)
BD.register(MyCallback())
BD.register(on_benders_end)
save(filename: str) → None

Save the statistics of the Benders decomposition process to a JSON file.

Parameters:

filename (str) – Path to the JSON file where the result will be saved.

solve() → None

Solve the problem using Benders decomposition.

This method implements the main Benders decomposition algorithm, iteratively solving the master and subproblems, adding cuts, and updating the results until convergence or stopping criteria are met.

After calling this method, the results and statistics of the Benders decomposition process can be accessed through the BendersSolver.result attribute, which is an instance of BendersResult.

class LShaped(master_problem: ~benderslib.core.MasterProblem, sub_problem: ~benderslib.core.SubProblems, complicating_vars: list[str], optimality_cut=<class 'benderslib.cuts.generators.LShapedOCGen'>, feasibility_cut=<class 'benderslib.cuts.generators.LShapedFCGen'>, params: ~benderslib.params.BendersParams | None = None)[source]

Bases: BendersSolver

An implementation of L-shaped Method (linear recourse).

It builds a Benders decomposition framework using the provided master problem, subproblem, and complicating variables. The optimality cut is defined by LShapedOC (single-cut) or ClassicalOC (multi-cut), and generated by LShapedOCGen; the feasibility cut is defined by ClassicalFC and generated by LShapedFCGen.

Note that L-shaped method is a generalization of classical Benders decomposition applied to two-stage stochastic programming problems. Therefore, ClassicalOC and ClassicalFC are also used in the L-shaped method.

Caution

The class LShaped requires the (second-stage) subproblems be pure LP.

Parameters:

  • master_problem (MasterProblem) – An instance of MasterProblem representing the master problem.

  • sub_problem (SubProblems) – An instance of SubProblems representing the collection of subproblems.

  • complicating_vars (list[str]) – A list of names of the complicating variables.

  • params (BendersParams, optional) – An instance of BendersParams containing parameters for the Benders decomposition process. If not provided, default parameters will be used.

Example

from benderslib import LShaped, MasterProblem, SubProblems
from benderslib.solvers import Gurobi

# Define master and subproblem models
master_model = ...  # Define your master problem model here
sub_models = [...]  # Define your list of subproblem models here
probs = [1/len(sub_models)] * len(sub_models)  # Define probabilities for each scenario

# Initialize master and subproblems
mp = MasterProblem(Gurobi(master_model))
sp = SubProblems([Gurobi(sm) for sm in sub_models], prob=probs)

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

# Initialize and solve
BD = LShaped(mp, sp, complicating_vars)
BD.solve()
classmethod from_models(master_model, master_solver, sub_model, sub_solver, complicating_vars, optimality_cut=<class 'benderslib.cuts.generators.LShapedOCGen'>, feasibility_cut=<class 'benderslib.cuts.generators.LShapedFCGen'>, prob=None, params: BendersParams | None = None)[source]

Class method to create a BendersSolver instance directly from solver models.

Parameters:

  • master_model – Solver model instance for the master problem (e.g., gurobipy.Model).

  • master_solver (Type[SolverBase]) – An abstract class that inherits from SolverBase to be used as the solver backend for the master problem.

  • sub_model – Solver model instance for the subproblem (e.g., gurobipy.Model).

  • sub_solver (Type[SolverBase]) – An abstract class that inherits from SolverBase to be used as the solver backend for the subproblem.

  • complicating_vars (list[str]) – A list of names of the complicating variables.

  • optimality_cut (Type[CutGenerator], optional) – An abstract class that inherits from CutGenerator to be used for generating optimality cuts. It also accepts a function with signature func(master_problem, sub_problem) -> list[OptimalityCut]. If None, no optimality cuts will be added.

  • feasibility_cut (Type[CutGenerator], optional) – An abstract class that inherits from CutGenerator to be used for generating feasibility cuts. It also accepts a function with signature func(master_problem, sub_problem) -> list[FeasibilityCut]. If None, no feasibility cuts will be added.

  • prob (list[float], optional) – A list of probabilities (or weights) for each subproblem when using multiple subproblems (L-shaped method).

  • params (BendersParams, optional) – The parameters that can be set by the user (see BendersParams). If not provided, default parameters will be used.

Example

from benderslib import BendersSolver
from benderslib.solvers import Gurobi
from gurobipy import Model

# Create master and subproblem models using Gurobi
master_model = Model()
# ... (define master problem variables, constraints, and objective)
sub_model = Model()
# ... (define subproblem variables, constraints, and objective)
complicating_vars = ['x1', 'x2']

# Create BendersSolver instance from models
benders_solver = BendersSolver.from_models(
    master_model = master_model,
    master_solver = Gurobi,
    sub_model = sub_model,
    sub_solver = Gurobi,
    complicating_vars = complicating_vars
)
bnc_solve()

Solve the problem using Branch-and-check method.

branch-and-check, or branch-and-Benders-cut, is a modern implementation of the Benders decomposition method that integrates the cut generation process into the branch-and-bound algorithm of the master problem solver. Instead of solving the master problem to optimality at each iteration, it checks the feasibility and optimality of the current solution at each node of the branch-and-bound tree and adds cuts as needed.

The Branch-and-check method is especially efficient when the subproblem is relatively easy to solve (than the master problem) and the number of cuts needed is large, as it avoids solving the master problem multiple times. However, it requires the master problem solver to support callback functions for adding cuts during the branch-and-bound process, which is supported by only a subset of solver interfaces.

When running Branch-and-check, BendersLib does not check whether the cut generated has been already added to the master problem, as another node may encounter the same solution and generate the same cut, which is not necessarily redundant in Branch-and-check. This differs from running the traditional Benders method using solve(), which warns users about duplicate cuts and skips adding them to the master problem.

The definition of the lower bound (and the gap) in Branch-and-check is different from the traditional Benders decomposition, as the master problem is not necessarily solved to optimality when cuts are added. Therefore, the master problem objective value at the current node may not be a valid lower bound for the original problem. In Branch-and-check, the lower bound is obtained from the best bound of the master problem at the current node. Therefore, users should be cautious when interpreting the results and statistics in Branch-and-check, and keep in mind that it is not directly comparable to the traditional Benders decomposition. The latter is usually stronger.

The runtime_master also differs from the traditional Benders decomposition, as there is not a clear separation that can be used to record the time of solving the master problem. In Branch-and-check, runtime_master simply equals the total runtime (runtime) minus the time spent on solving the subproblem (runtime_sub).

This method can also be used by setting use_bnc to True and calling solve(), which will internally call this method.

Caution

The method bnc_solve() is incompatible with Benders decomposition instances that have a purely continuous master problem. This is because the Branch-and-check method generates cuts on nodes of the branch-and-bound tree, which does not exist for Linear Programming problems.

Example

BD = BendersSolver(...)

BD.bnc_solve()
# or equivalently
BD.params.use_bnc = True
BD.solve()
register(callback: CallbackBase | Callable | Type[CallbackBase]) → None

Register a user-defined callback to be called during the Benders solving process.

Users can define custom callbacks by inheriting from CallbackBase and overriding the desired event methods. Each method receives a BendersContext object containing information about the current state of the Benders decomposition process. Alternatively, users can define standalone functions with names matching the methods in CallbackBase to serve as lightweight callbacks.

Parameters:

callback (CallbackBase | Callable | Type[CallbackBase]) – A callback instance (or class) inherited from CallbackBase or a function with signature func(context: BendersContext) -> CST.PROCEED | CST.TERMINATE | None.

Example

from benderslib.callback import CallbackBase, BendersContext

# Class-based callback
class MyCallback(CallbackBase):

    def on_benders_start(self, context: BendersContext):
        print("Benders process started!")

# Function-based callback
def on_benders_end(self, context: BendersContext):
    print("Benders process finished!")

BD = BendersSolver(...)
BD.register(MyCallback())
BD.register(on_benders_end)
save(filename: str) → None

Save the statistics of the Benders decomposition process to a JSON file.

Parameters:

filename (str) – Path to the JSON file where the result will be saved.

solve() → None

Solve the problem using Benders decomposition.

This method implements the main Benders decomposition algorithm, iteratively solving the master and subproblems, adding cuts, and updating the results until convergence or stopping criteria are met.

After calling this method, the results and statistics of the Benders decomposition process can be accessed through the BendersSolver.result attribute, which is an instance of BendersResult.

class IntegerLShaped(master_problem: ~benderslib.core.MasterProblem, sub_problem: ~benderslib.core.SubProblems, complicating_vars: list[str], optimality_cut=<class 'benderslib.cuts.generators.IntegerLShapedOCGen'>, feasibility_cut=<class 'benderslib.cuts.generators.IntegerLShapedFCGen'>, params: ~benderslib.params.BendersParams | None = None)[source]

Bases: BendersSolver

An implementation of Integer L-shaped Method.

It is for two-stage stochastic programming with binary complicating variables and integer recourse. It builds a Benders decomposition framework using the provided master problem, subproblem, and complicating variables. The optimality cut is defined by CombinatorialOC and generated by IntegerLShapedOCGen; the feasibility cut is defined by NoGoodFC and generated by IntegerLShapedFCGen.

The integer L-shaped method is an extension of the L-shaped method and the Combinatorial Benders decomposition to solve two-stage stochastic integer programming problems. The cut used in this method are the same as those in Combinatorial Benders decomposition, and the algorithmic framework is similar to that of the L-shaped method.

Caution

The class IntegerLShaped requires the complicating variables to be pure binary (0-1), integer variables in the subproblems are allowed.

Parameters:

  • master_problem (MasterProblem) – An instance of MasterProblem representing the master problem.

  • sub_problem (SubProblems) – An instance of SubProblems representing the collection of subproblems.

  • complicating_vars (list[str]) – A list of names of the binary complicating variables in the master problem.

  • params (BendersParams, optional) – An instance of BendersParams containing parameters for the Benders decomposition process. If not provided, default parameters will be used.

Example

from benderslib import IntegerLShaped, MasterProblem, SubProblems
from benderslib.solvers import Gurobi

# Define master and subproblem models
master_model = ...  # Define your master problem model here
sub_models = [...]  # Define your list of subproblem models here
probs = [1/len(sub_models)] * len(sub_models)  # Define probabilities for each scenario

# Initialize master and subproblems
mp = MasterProblem(Gurobi(master_model))
sp = SubProblems([Gurobi(sm) for sm in sub_models], prob=probs)

# Define complicating variables (must be binary)
complicating_vars = ['x1', 'x2', 'x3']

# Initialize and solve
BD = IntegerLShaped(mp, sp, complicating_vars)
BD.solve()
classmethod from_models(master_model, master_solver, sub_model, sub_solver, complicating_vars, optimality_cut=<class 'benderslib.cuts.generators.IntegerLShapedOCGen'>, feasibility_cut=<class 'benderslib.cuts.generators.IntegerLShapedFCGen'>, prob=None, params: BendersParams | None = None)[source]

Class method to create a BendersSolver instance directly from solver models.

Parameters:

  • master_model – Solver model instance for the master problem (e.g., gurobipy.Model).

  • master_solver (Type[SolverBase]) – An abstract class that inherits from SolverBase to be used as the solver backend for the master problem.

  • sub_model – Solver model instance for the subproblem (e.g., gurobipy.Model).

  • sub_solver (Type[SolverBase]) – An abstract class that inherits from SolverBase to be used as the solver backend for the subproblem.

  • complicating_vars (list[str]) – A list of names of the complicating variables.

  • optimality_cut (Type[CutGenerator], optional) – An abstract class that inherits from CutGenerator to be used for generating optimality cuts. It also accepts a function with signature func(master_problem, sub_problem) -> list[OptimalityCut]. If None, no optimality cuts will be added.

  • feasibility_cut (Type[CutGenerator], optional) – An abstract class that inherits from CutGenerator to be used for generating feasibility cuts. It also accepts a function with signature func(master_problem, sub_problem) -> list[FeasibilityCut]. If None, no feasibility cuts will be added.

  • prob (list[float], optional) – A list of probabilities (or weights) for each subproblem when using multiple subproblems (L-shaped method).

  • params (BendersParams, optional) – The parameters that can be set by the user (see BendersParams). If not provided, default parameters will be used.

Example

from benderslib import BendersSolver
from benderslib.solvers import Gurobi
from gurobipy import Model

# Create master and subproblem models using Gurobi
master_model = Model()
# ... (define master problem variables, constraints, and objective)
sub_model = Model()
# ... (define subproblem variables, constraints, and objective)
complicating_vars = ['x1', 'x2']

# Create BendersSolver instance from models
benders_solver = BendersSolver.from_models(
    master_model = master_model,
    master_solver = Gurobi,
    sub_model = sub_model,
    sub_solver = Gurobi,
    complicating_vars = complicating_vars
)
bnc_solve()

Solve the problem using Branch-and-check method.

branch-and-check, or branch-and-Benders-cut, is a modern implementation of the Benders decomposition method that integrates the cut generation process into the branch-and-bound algorithm of the master problem solver. Instead of solving the master problem to optimality at each iteration, it checks the feasibility and optimality of the current solution at each node of the branch-and-bound tree and adds cuts as needed.

The Branch-and-check method is especially efficient when the subproblem is relatively easy to solve (than the master problem) and the number of cuts needed is large, as it avoids solving the master problem multiple times. However, it requires the master problem solver to support callback functions for adding cuts during the branch-and-bound process, which is supported by only a subset of solver interfaces.

When running Branch-and-check, BendersLib does not check whether the cut generated has been already added to the master problem, as another node may encounter the same solution and generate the same cut, which is not necessarily redundant in Branch-and-check. This differs from running the traditional Benders method using solve(), which warns users about duplicate cuts and skips adding them to the master problem.

The definition of the lower bound (and the gap) in Branch-and-check is different from the traditional Benders decomposition, as the master problem is not necessarily solved to optimality when cuts are added. Therefore, the master problem objective value at the current node may not be a valid lower bound for the original problem. In Branch-and-check, the lower bound is obtained from the best bound of the master problem at the current node. Therefore, users should be cautious when interpreting the results and statistics in Branch-and-check, and keep in mind that it is not directly comparable to the traditional Benders decomposition. The latter is usually stronger.

The runtime_master also differs from the traditional Benders decomposition, as there is not a clear separation that can be used to record the time of solving the master problem. In Branch-and-check, runtime_master simply equals the total runtime (runtime) minus the time spent on solving the subproblem (runtime_sub).

This method can also be used by setting use_bnc to True and calling solve(), which will internally call this method.

Caution

The method bnc_solve() is incompatible with Benders decomposition instances that have a purely continuous master problem. This is because the Branch-and-check method generates cuts on nodes of the branch-and-bound tree, which does not exist for Linear Programming problems.

Example

BD = BendersSolver(...)

BD.bnc_solve()
# or equivalently
BD.params.use_bnc = True
BD.solve()
register(callback: CallbackBase | Callable | Type[CallbackBase]) → None

Register a user-defined callback to be called during the Benders solving process.

Users can define custom callbacks by inheriting from CallbackBase and overriding the desired event methods. Each method receives a BendersContext object containing information about the current state of the Benders decomposition process. Alternatively, users can define standalone functions with names matching the methods in CallbackBase to serve as lightweight callbacks.

Parameters:

callback (CallbackBase | Callable | Type[CallbackBase]) – A callback instance (or class) inherited from CallbackBase or a function with signature func(context: BendersContext) -> CST.PROCEED | CST.TERMINATE | None.

Example

from benderslib.callback import CallbackBase, BendersContext

# Class-based callback
class MyCallback(CallbackBase):

    def on_benders_start(self, context: BendersContext):
        print("Benders process started!")

# Function-based callback
def on_benders_end(self, context: BendersContext):
    print("Benders process finished!")

BD = BendersSolver(...)
BD.register(MyCallback())
BD.register(on_benders_end)
save(filename: str) → None

Save the statistics of the Benders decomposition process to a JSON file.

Parameters:

filename (str) – Path to the JSON file where the result will be saved.

solve() → None

Solve the problem using Benders decomposition.

This method implements the main Benders decomposition algorithm, iteratively solving the master and subproblems, adding cuts, and updating the results until convergence or stopping criteria are met.

After calling this method, the results and statistics of the Benders decomposition process can be accessed through the BendersSolver.result attribute, which is an instance of BendersResult.

class LogicBasedBenders(master_problem: MasterProblem, sub_problem: LogicBasedSubProblem | SubProblem | Callable | SubProblems, complicating_vars: list[str], optimality_cut: Type[CutGenerator] | Callable | None = None, feasibility_cut: Type[CutGenerator] | Callable | None = None, params: BendersParams | None = None)[source]

Bases: BendersSolver

An implementation of Logic-based Benders Decomposition.

The Logic-based Benders Decomposition is highly customizable. When using non-standard solvers that are not natively supported by BendersLib (typically heuristics or exact algorithms), users need to define their own subproblem, inheriting from LogicBasedSubProblem. Users also need to implement their own optimality/feasibility cut generator, inheriting from CutGenerator.

Parameters:

  • master_problem (MasterProblem) – An instance of MasterProblem representing the master problem.

  • sub_problem (LogicBasedSubProblem | SubProblem | Callable | SubProblems) – An instance of LogicBasedSubProblem representing the subproblem. Alternatively, users can provide a function that takes the values of complicating variables as input and returns the optimal objective value and cut information.

  • complicating_vars (list[str]) – A list of names of the complicating variables.

  • optimality_cut (Type[CutGenerator] | Callable | None, optional) – A class inheriting from CutGenerator (or a function) to generate optimality cuts. If not provided, no optimality cut will be added.

  • feasibility_cut (Type[CutGenerator] | Callable | None, optional) – A class inheriting from CutGenerator (or a function) to generate feasibility cuts. If not provided, no feasibility cut will be added.

  • params (BendersParams, optional) – An instance of BendersParams containing parameters for the Benders decomposition process. If not provided, default parameters will be used.

Example

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()
bnc_solve()

Solve the problem using Branch-and-check method.

branch-and-check, or branch-and-Benders-cut, is a modern implementation of the Benders decomposition method that integrates the cut generation process into the branch-and-bound algorithm of the master problem solver. Instead of solving the master problem to optimality at each iteration, it checks the feasibility and optimality of the current solution at each node of the branch-and-bound tree and adds cuts as needed.

The Branch-and-check method is especially efficient when the subproblem is relatively easy to solve (than the master problem) and the number of cuts needed is large, as it avoids solving the master problem multiple times. However, it requires the master problem solver to support callback functions for adding cuts during the branch-and-bound process, which is supported by only a subset of solver interfaces.

When running Branch-and-check, BendersLib does not check whether the cut generated has been already added to the master problem, as another node may encounter the same solution and generate the same cut, which is not necessarily redundant in Branch-and-check. This differs from running the traditional Benders method using solve(), which warns users about duplicate cuts and skips adding them to the master problem.

The definition of the lower bound (and the gap) in Branch-and-check is different from the traditional Benders decomposition, as the master problem is not necessarily solved to optimality when cuts are added. Therefore, the master problem objective value at the current node may not be a valid lower bound for the original problem. In Branch-and-check, the lower bound is obtained from the best bound of the master problem at the current node. Therefore, users should be cautious when interpreting the results and statistics in Branch-and-check, and keep in mind that it is not directly comparable to the traditional Benders decomposition. The latter is usually stronger.

The runtime_master also differs from the traditional Benders decomposition, as there is not a clear separation that can be used to record the time of solving the master problem. In Branch-and-check, runtime_master simply equals the total runtime (runtime) minus the time spent on solving the subproblem (runtime_sub).

This method can also be used by setting use_bnc to True and calling solve(), which will internally call this method.

Caution

The method bnc_solve() is incompatible with Benders decomposition instances that have a purely continuous master problem. This is because the Branch-and-check method generates cuts on nodes of the branch-and-bound tree, which does not exist for Linear Programming problems.

Example

BD = BendersSolver(...)

BD.bnc_solve()
# or equivalently
BD.params.use_bnc = True
BD.solve()
classmethod from_models(master_model, master_solver: Type[SolverBase], sub_model, sub_solver: Type[SolverBase], complicating_vars: list[str], optimality_cut: Type[CutGenerator] | Callable = None, feasibility_cut: Type[CutGenerator] | Callable = None, prob: list[float] | None = None, params: BendersParams | None = None)

Class method to create a BendersSolver instance directly from solver models.

Parameters:

  • master_model – Solver model instance for the master problem (e.g., gurobipy.Model).

  • master_solver (Type[SolverBase]) – An abstract class that inherits from SolverBase to be used as the solver backend for the master problem.

  • sub_model – Solver model instance for the subproblem (e.g., gurobipy.Model).

  • sub_solver (Type[SolverBase]) – An abstract class that inherits from SolverBase to be used as the solver backend for the subproblem.

  • complicating_vars (list[str]) – A list of names of the complicating variables.

  • optimality_cut (Type[CutGenerator], optional) – An abstract class that inherits from CutGenerator to be used for generating optimality cuts. It also accepts a function with signature func(master_problem, sub_problem) -> list[OptimalityCut]. If None, no optimality cuts will be added.

  • feasibility_cut (Type[CutGenerator], optional) – An abstract class that inherits from CutGenerator to be used for generating feasibility cuts. It also accepts a function with signature func(master_problem, sub_problem) -> list[FeasibilityCut]. If None, no feasibility cuts will be added.

  • prob (list[float], optional) – A list of probabilities (or weights) for each subproblem when using multiple subproblems (L-shaped method).

  • params (BendersParams, optional) – The parameters that can be set by the user (see BendersParams). If not provided, default parameters will be used.

Example

from benderslib import BendersSolver
from benderslib.solvers import Gurobi
from gurobipy import Model

# Create master and subproblem models using Gurobi
master_model = Model()
# ... (define master problem variables, constraints, and objective)
sub_model = Model()
# ... (define subproblem variables, constraints, and objective)
complicating_vars = ['x1', 'x2']

# Create BendersSolver instance from models
benders_solver = BendersSolver.from_models(
    master_model = master_model,
    master_solver = Gurobi,
    sub_model = sub_model,
    sub_solver = Gurobi,
    complicating_vars = complicating_vars
)
register(callback: CallbackBase | Callable | Type[CallbackBase]) → None

Register a user-defined callback to be called during the Benders solving process.

Users can define custom callbacks by inheriting from CallbackBase and overriding the desired event methods. Each method receives a BendersContext object containing information about the current state of the Benders decomposition process. Alternatively, users can define standalone functions with names matching the methods in CallbackBase to serve as lightweight callbacks.

Parameters:

callback (CallbackBase | Callable | Type[CallbackBase]) – A callback instance (or class) inherited from CallbackBase or a function with signature func(context: BendersContext) -> CST.PROCEED | CST.TERMINATE | None.

Example

from benderslib.callback import CallbackBase, BendersContext

# Class-based callback
class MyCallback(CallbackBase):

    def on_benders_start(self, context: BendersContext):
        print("Benders process started!")

# Function-based callback
def on_benders_end(self, context: BendersContext):
    print("Benders process finished!")

BD = BendersSolver(...)
BD.register(MyCallback())
BD.register(on_benders_end)
save(filename: str) → None

Save the statistics of the Benders decomposition process to a JSON file.

Parameters:

filename (str) – Path to the JSON file where the result will be saved.

solve() → None

Solve the problem using Benders decomposition.

This method implements the main Benders decomposition algorithm, iteratively solving the master and subproblems, adding cuts, and updating the results until convergence or stopping criteria are met.

After calling this method, the results and statistics of the Benders decomposition process can be accessed through the BendersSolver.result attribute, which is an instance of BendersResult.

class GeneLShaped(master_problem: ~benderslib.core.MasterProblem, sub_problem: ~benderslib.core.SubProblems, complicating_vars: list[str], optimality_cut=<class 'benderslib.cuts.generators.GeneLShapedOCGen'>, feasibility_cut=<class 'benderslib.cuts.generators.LShapedFCGen'>, params: ~benderslib.params.BendersParams | None = None)[source]

Bases: BendersSolver

An implementation of L-shaped Method (convex recourse).

This method extends the L-shaped method to two-stage stochastic programming problems with convex second-stage (recourse) problems. It combines the multi-scenario framework of the L-shaped method with the cut generation principles of Generalized Benders Decomposition.

The optimality cut is defined by GeneLShapedOC (single-cut) or GeneralizedOC (multi-cut), and generated by GeneLShapedOCGen. The feasibility cut is defined by ClassicalFC and generated by LShapedFCGen.

Caution

The class GeneLShaped requires the second-stage subproblems be convex. The requirements to original problems, master problems and subproblems in GeneralizedBenders also apply here.

Parameters:

  • master_problem (MasterProblem) – An instance of MasterProblem representing the master problem.

  • sub_problem (SubProblems) – An instance of SubProblems representing the collection of subproblems.

  • complicating_vars (list[str]) – A list of names of the complicating variables.

  • params (BendersParams, optional) – An instance of BendersParams containing parameters for the Benders decomposition process. If not provided, default parameters will be used.

Example

from benderslib import GeneLShaped, MasterProblem, SubProblems
from benderslib.solvers import Gurobi

# Define master and subproblem models
master_model = ...  # Define your master problem model here
sub_models = [...]  # Define your list of convex subproblem models here
probs = [1/len(sub_models)] * len(sub_models)  # Define probabilities for each scenario

# Initialize master and subproblems
mp = MasterProblem(Gurobi(master_model))
sp = SubProblems([Gurobi(sm) for sm in sub_models], prob=probs)

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

# Initialize and solve
BD = GeneLShaped(mp, sp, complicating_vars)
BD.solve()
classmethod from_models(master_model, master_solver, sub_model, sub_solver, complicating_vars, optimality_cut=<class 'benderslib.cuts.generators.GeneLShapedOCGen'>, feasibility_cut=<class 'benderslib.cuts.generators.LShapedFCGen'>, prob=None, params: BendersParams | None = None)[source]

Class method to create a BendersSolver instance directly from solver models.

Parameters:

  • master_model – Solver model instance for the master problem (e.g., gurobipy.Model).

  • master_solver (Type[SolverBase]) – An abstract class that inherits from SolverBase to be used as the solver backend for the master problem.

  • sub_model – Solver model instance for the subproblem (e.g., gurobipy.Model).

  • sub_solver (Type[SolverBase]) – An abstract class that inherits from SolverBase to be used as the solver backend for the subproblem.

  • complicating_vars (list[str]) – A list of names of the complicating variables.

  • optimality_cut (Type[CutGenerator], optional) – An abstract class that inherits from CutGenerator to be used for generating optimality cuts. It also accepts a function with signature func(master_problem, sub_problem) -> list[OptimalityCut]. If None, no optimality cuts will be added.

  • feasibility_cut (Type[CutGenerator], optional) – An abstract class that inherits from CutGenerator to be used for generating feasibility cuts. It also accepts a function with signature func(master_problem, sub_problem) -> list[FeasibilityCut]. If None, no feasibility cuts will be added.

  • prob (list[float], optional) – A list of probabilities (or weights) for each subproblem when using multiple subproblems (L-shaped method).

  • params (BendersParams, optional) – The parameters that can be set by the user (see BendersParams). If not provided, default parameters will be used.

Example

from benderslib import BendersSolver
from benderslib.solvers import Gurobi
from gurobipy import Model

# Create master and subproblem models using Gurobi
master_model = Model()
# ... (define master problem variables, constraints, and objective)
sub_model = Model()
# ... (define subproblem variables, constraints, and objective)
complicating_vars = ['x1', 'x2']

# Create BendersSolver instance from models
benders_solver = BendersSolver.from_models(
    master_model = master_model,
    master_solver = Gurobi,
    sub_model = sub_model,
    sub_solver = Gurobi,
    complicating_vars = complicating_vars
)
bnc_solve()

Solve the problem using Branch-and-check method.

branch-and-check, or branch-and-Benders-cut, is a modern implementation of the Benders decomposition method that integrates the cut generation process into the branch-and-bound algorithm of the master problem solver. Instead of solving the master problem to optimality at each iteration, it checks the feasibility and optimality of the current solution at each node of the branch-and-bound tree and adds cuts as needed.

The Branch-and-check method is especially efficient when the subproblem is relatively easy to solve (than the master problem) and the number of cuts needed is large, as it avoids solving the master problem multiple times. However, it requires the master problem solver to support callback functions for adding cuts during the branch-and-bound process, which is supported by only a subset of solver interfaces.

When running Branch-and-check, BendersLib does not check whether the cut generated has been already added to the master problem, as another node may encounter the same solution and generate the same cut, which is not necessarily redundant in Branch-and-check. This differs from running the traditional Benders method using solve(), which warns users about duplicate cuts and skips adding them to the master problem.

The definition of the lower bound (and the gap) in Branch-and-check is different from the traditional Benders decomposition, as the master problem is not necessarily solved to optimality when cuts are added. Therefore, the master problem objective value at the current node may not be a valid lower bound for the original problem. In Branch-and-check, the lower bound is obtained from the best bound of the master problem at the current node. Therefore, users should be cautious when interpreting the results and statistics in Branch-and-check, and keep in mind that it is not directly comparable to the traditional Benders decomposition. The latter is usually stronger.

The runtime_master also differs from the traditional Benders decomposition, as there is not a clear separation that can be used to record the time of solving the master problem. In Branch-and-check, runtime_master simply equals the total runtime (runtime) minus the time spent on solving the subproblem (runtime_sub).

This method can also be used by setting use_bnc to True and calling solve(), which will internally call this method.

Caution

The method bnc_solve() is incompatible with Benders decomposition instances that have a purely continuous master problem. This is because the Branch-and-check method generates cuts on nodes of the branch-and-bound tree, which does not exist for Linear Programming problems.

Example

BD = BendersSolver(...)

BD.bnc_solve()
# or equivalently
BD.params.use_bnc = True
BD.solve()
register(callback: CallbackBase | Callable | Type[CallbackBase]) → None

Register a user-defined callback to be called during the Benders solving process.

Users can define custom callbacks by inheriting from CallbackBase and overriding the desired event methods. Each method receives a BendersContext object containing information about the current state of the Benders decomposition process. Alternatively, users can define standalone functions with names matching the methods in CallbackBase to serve as lightweight callbacks.

Parameters:

callback (CallbackBase | Callable | Type[CallbackBase]) – A callback instance (or class) inherited from CallbackBase or a function with signature func(context: BendersContext) -> CST.PROCEED | CST.TERMINATE | None.

Example

from benderslib.callback import CallbackBase, BendersContext

# Class-based callback
class MyCallback(CallbackBase):

    def on_benders_start(self, context: BendersContext):
        print("Benders process started!")

# Function-based callback
def on_benders_end(self, context: BendersContext):
    print("Benders process finished!")

BD = BendersSolver(...)
BD.register(MyCallback())
BD.register(on_benders_end)
save(filename: str) → None

Save the statistics of the Benders decomposition process to a JSON file.

Parameters:

filename (str) – Path to the JSON file where the result will be saved.

solve() → None

Solve the problem using Benders decomposition.

This method implements the main Benders decomposition algorithm, iteratively solving the master and subproblems, adding cuts, and updating the results until convergence or stopping criteria are met.

After calling this method, the results and statistics of the Benders decomposition process can be accessed through the BendersSolver.result attribute, which is an instance of BendersResult.

class AnnotatedBenders(original_problem, solver: Type[SolverBase], complicating_vars: list[str], master_vars: list[str] = None, benders: Type[BendersSolver] = None, optimality_cut=None, feasibility_cut=None, params: BendersParams | None = None)[source]

Bases: BendersSolver

The class to perform Benders decomposition using annotation-based approach.

This class decomposes the original problem into a master problem and a subproblem based on the specified complicating/master variables, and then applies the chosen Benders decomposition method to solve the problem.

Master problem variables vs. complicating variables

The master problem variables are variables that appears only in the master problem. It has a subset, complicating variables, which are variables that are passed to the subproblem as known parameters. Though they are sometimes identical, the decomposition is based on the former.

Parameters:

  • original_problem – The original optimization problem in a solver-specific format.

  • solver (Type[SolverBase]) – The solver class to be used for solving the master and subproblems, e.g., Gurobi. It should be compatible with the original_problem.

  • complicating_vars (list[str]) – A list of variable names that are considered complicating variables for the decomposition. The complicating variables are those that are passed to the subproblem as known parameters.

  • master_vars (list[str], optional) – A list of variable names to be included in the master problem. The master variables are used to define the master problem and subproblem from the original problem. It is usually a superset of complicating_vars. If not provided, it defaults to complicating_vars.

  • benders (Type[BendersSolver], optional) – The Benders decomposition method to be applied, e.g., ClassicalBenders. If not provided, the class BendersSolver will be used with the optimality and feasibility cut generators provided. If provided, parameters optimality_cut and feasibility_cut will be ignored, and the default cut generators of the chosen Benders method will be used.

  • optimality_cut (Type[CutGenerator], optional) – The optimality cut generator to be used in the Benders decomposition. If not provided, the default optimality cut generator of the chosen Benders method benders will be used.

  • feasibility_cut (Type[CutGenerator], optional) – The feasibility cut generator to be used in the Benders decomposition. If not provided, the default feasibility cut generator of the chosen Benders method benders will be used.

  • params (BendersParams, optional) – An instance of BendersParams containing parameters for the Benders decomposition process. If not provided, default parameters will be used.

Caution

  • The solver should be a class (not an instance) that inherits from SolverBase.

  • The benders should be a class (not an instance) that inherits from BendersSolver.

  • The optimality_cut and feasibility_cut, if provided, should be classes (not instances) that inherit from CutGenerator.

Example

from benderslib import AnnotatedBenders, ClassicalBenders
from benderslib.solvers import Gurobi

original_problem = ...  # Define or load your original problem here
complicating_vars = [...]  # List of complicating variable names
master_vars = [...]  # List of master variable names (usually a superset of complicating_vars)

BD = AnnotatedBenders(
    original_problem=original_problem,
    solver=Gurobi,
    benders=ClassicalBenders,
    complicating_vars=complicating_vars,
    master_vars=master_vars
)
static decompose(original_problem, solver: Type[SolverBase], master_vars: list[str], solver_model=False) → tuple[source]

Decomposes the original problem into a master problem and a subproblem.

It conducts automatic decomposition based on the given master variable names, using the methods make_master_problem() and make_sub_problem() provided by the solver interfaces.

Master problem variables vs. complicating variables

The master problem variables are variables that appears only in the master problem. It has a subset, complicating variables, which are variables that are passed to the subproblem as known parameters. Though they are sometimes identical, the decomposition is based on the former.

Parameters:

  • original_problem – The original optimization problem in a solver-specific format.

  • solver (Type[SolverBase]) – The solver class to be used for solving the master and subproblems.

  • master_vars (list[str]) – A list of variable names to be included in the master problem.

  • solver_model (bool, optional) – If True, return the master and subproblem in the solver-specific format; If False, return instances of MasterProblem and SubProblem.

Returns:

A tuple containing the master problem and subproblem instances.

Return type:

tuple[MasterProblem, SubProblem] | tuple[object, object]

Example

from benderslib import AnnotatedBenders
from benderslib.solvers import Gurobi

original_problem = ...  # Define or load your original problem here
master_vars = [...]  # List of master variable names (usually a superset of complicating_vars)

master, sub = AnnotatedBenders.decompose(
    original_problem=original_problem,
    solver=Gurobi,
    master_vars=master_vars,
    solver_model=False  # (Default) Returns MasterProblem and SubProblem instances
)
bnc_solve()

Solve the problem using Branch-and-check method.

branch-and-check, or branch-and-Benders-cut, is a modern implementation of the Benders decomposition method that integrates the cut generation process into the branch-and-bound algorithm of the master problem solver. Instead of solving the master problem to optimality at each iteration, it checks the feasibility and optimality of the current solution at each node of the branch-and-bound tree and adds cuts as needed.

The Branch-and-check method is especially efficient when the subproblem is relatively easy to solve (than the master problem) and the number of cuts needed is large, as it avoids solving the master problem multiple times. However, it requires the master problem solver to support callback functions for adding cuts during the branch-and-bound process, which is supported by only a subset of solver interfaces.

When running Branch-and-check, BendersLib does not check whether the cut generated has been already added to the master problem, as another node may encounter the same solution and generate the same cut, which is not necessarily redundant in Branch-and-check. This differs from running the traditional Benders method using solve(), which warns users about duplicate cuts and skips adding them to the master problem.

The definition of the lower bound (and the gap) in Branch-and-check is different from the traditional Benders decomposition, as the master problem is not necessarily solved to optimality when cuts are added. Therefore, the master problem objective value at the current node may not be a valid lower bound for the original problem. In Branch-and-check, the lower bound is obtained from the best bound of the master problem at the current node. Therefore, users should be cautious when interpreting the results and statistics in Branch-and-check, and keep in mind that it is not directly comparable to the traditional Benders decomposition. The latter is usually stronger.

The runtime_master also differs from the traditional Benders decomposition, as there is not a clear separation that can be used to record the time of solving the master problem. In Branch-and-check, runtime_master simply equals the total runtime (runtime) minus the time spent on solving the subproblem (runtime_sub).

This method can also be used by setting use_bnc to True and calling solve(), which will internally call this method.

Caution

The method bnc_solve() is incompatible with Benders decomposition instances that have a purely continuous master problem. This is because the Branch-and-check method generates cuts on nodes of the branch-and-bound tree, which does not exist for Linear Programming problems.

Example

BD = BendersSolver(...)

BD.bnc_solve()
# or equivalently
BD.params.use_bnc = True
BD.solve()
register(callback: CallbackBase | Callable | Type[CallbackBase]) → None

Register a user-defined callback to be called during the Benders solving process.

Users can define custom callbacks by inheriting from CallbackBase and overriding the desired event methods. Each method receives a BendersContext object containing information about the current state of the Benders decomposition process. Alternatively, users can define standalone functions with names matching the methods in CallbackBase to serve as lightweight callbacks.

Parameters:

callback (CallbackBase | Callable | Type[CallbackBase]) – A callback instance (or class) inherited from CallbackBase or a function with signature func(context: BendersContext) -> CST.PROCEED | CST.TERMINATE | None.

Example

from benderslib.callback import CallbackBase, BendersContext

# Class-based callback
class MyCallback(CallbackBase):

    def on_benders_start(self, context: BendersContext):
        print("Benders process started!")

# Function-based callback
def on_benders_end(self, context: BendersContext):
    print("Benders process finished!")

BD = BendersSolver(...)
BD.register(MyCallback())
BD.register(on_benders_end)
save(filename: str) → None

Save the statistics of the Benders decomposition process to a JSON file.

Parameters:

filename (str) – Path to the JSON file where the result will be saved.

solve() → None

Solve the problem using Benders decomposition.

This method implements the main Benders decomposition algorithm, iteratively solving the master and subproblems, adding cuts, and updating the results until convergence or stopping criteria are met.

After calling this method, the results and statistics of the Benders decomposition process can be accessed through the BendersSolver.result attribute, which is an instance of BendersResult.

Cut Generators

class ClassicalOCGen(master_problem, sub_problem, params)[source]

Bases: CutGenerator

The optimality cut generator for Classical Benders Decomposition.

generate() → list[ClassicalOC][source]

This method generates ClassicalOC optimality cuts based on the current solution of the master problem and the dual values obtained from the subproblem.

class ClassicalFCGen(master_problem, sub_problem, params)[source]

Bases: CutGenerator

The feasibility cut generator for Classical Benders Decomposition.

generate() → list[ClassicalFC][source]

This method generates ClassicalFC feasibility cuts based on the current solution of the master problem and the extreme ray obtained from the subproblem.

class CombinatorialOCGen(master_problem, sub_problem, params)[source]

Bases: CutGenerator

The optimality cut generator for Combinatorial Benders Decomposition.

generate() → list[CombinatorialOC][source]

This method generates CombinatorialOC optimality cuts based on the current solution of the master problem and the objective value obtained from the subproblem.

class CombinatorialFCGen(master_problem, sub_problem, params)[source]

Bases: CutGenerator

The feasibility cut generator for Combinatorial Benders Decomposition.

generate() → list[NoGoodFC][source]

This method generates NoGoodFC feasibility cuts based on the current solution of the master problem.

class LShapedOCGen(master_problem, sub_problem, params)[source]

Bases: CutGenerator

The optimality cut generator for L-shaped Method (linear recourse).

generate() → list[ClassicalOC] | list[LShapedOC][source]

This method generates optimality cuts based on the current solution of the master problem and the dual values obtained from the subproblems. If BendersParams.multi_opti_cut is True, _multi_cuts() is called to generate multiple cuts; otherwise, _single_cut() is called to generate a single aggregated cut.

class LShapedFCGen(master_problem, sub_problem, params)[source]

Bases: CutGenerator

The feasibility cut generator for L-shaped Method.

generate() → list[ClassicalFC][source]

This method generates ClassicalFC feasibility cuts based on the current solution of the master problem and the extreme rays obtained from the subproblems.

class IntegerLShapedOCGen(master_problem, sub_problem, params)[source]

Bases: CutGenerator

The optimality cut generator for Integer L-shaped Method.

generate()[source]

This method generates optimality cuts based on the current values of binary complicating variables in the master problem and the objective values obtained from the subproblems. If BendersParams.multi_opti_cut is True, _multi_cuts() is called to generate multiple cuts; otherwise, _single_cut() is called to generate a single aggregated cut.

class IntegerLShapedFCGen(master_problem, sub_problem, params)[source]

Bases: CutGenerator

The feasibility cut generator for Integer L-shaped Method.

generate() → list[NoGoodFC][source]

This method generates NoGoodFC feasibility cuts based on the current values of binary complicating variables in the master problem.

class GeneralizedOCGen(master_problem, sub_problem, params)[source]

Bases: CutGenerator

The optimality cut generator for Generalized Benders Decomposition.

generate() → list[GeneralizedOC][source]

This method generates GeneralizedOC optimality cuts.

class GeneralizedFCGen(master_problem, sub_problem, params)[source]

Bases: CutGenerator

The feasibility cut generator for Generalized Benders Decomposition.

generate() → list[ClassicalFC][source]

This method generates GeneralizedFC feasibility cuts.

class GeneLShapedOCGen(master_problem, sub_problem, params)[source]

Bases: CutGenerator

The optimality cut generator for L-shaped Method (convex recourse).

generate() → list[GeneLShapedOC] | list[GeneralizedOC][source]

Generates optimality cuts for the generalized L-shaped method.

If BendersParams.multi_opti_cut is True, this method calls _multi_cuts() to generate multiple GeneralizedOC, one for each violated scenario; If False, it calls _single_cut() to generate one aggregated GeneLShapedOC for all scenarios.