Core Classes¶

Benders Cut¶

class Cut(vars: list[str], coefs: list[float | int], rhs: float | int, sense: str, ctype: OPTIMAL | FEASIBILITY, name: str)[source]¶

Bases: object

The base class for Benders cuts in Benders decomposition.

Parameters:

vars (list[str]) – The list of variable names involved in the cut.
coefs (list[float | int]) – The list of coefficients corresponding to the variables in the cut.
rhs (float | int) – The right-hand side value of the cut.
sense (str) – The sense of the cut (LE, GE, or EQ).
ctype (str) – It should be OPTIMALITY or FEASIBILITY.
name (str) – The name for the cut.

Example

from benderslib import Cut, CST

cut = Cut(
    vars=['x1', 'x2'],
    coefs=[1.0, -2.0],
    rhs=5.0,
    sense=CST.LE,
    ctype=CST.OPTIMALITY,
    name='MyCut'
)

vars: list[str]¶: The list of variable names involved in the cut.

coefs: list[float | int]¶: The list of coefficients corresponding to the variables in the cut.

rhs: float | int¶: The right-hand side value of the cut.

sense: str¶

The sense of the cut.

It must be LE, GE, or EQ.

ctype: CST.OPTIMAL | CST.FEASIBILITY¶

The indicator of the cut type.

It should be either OPTIMALITY or FEASIBILITY.

name: str¶: The name for the cut.

class OptimalityCut(vars, coefs, rhs, sense, name='OC')[source]¶

Bases: Cut

The class of optimality cuts in Benders decomposition.

Parameters:

vars (list[str]) – A list of variable names involved in the cut.
coefs (list[float | int]) – A list of coefficients corresponding to the variables in the cut.
rhs (float | int) – The right-hand side value of the cut.
sense (str) – The sense of the cut, must be in senses.
name (str) – A name for the cut.

Example

from benderslib import OptimalityCut, CST

oc = OptimalityCut(
    vars=['x1', 'x2'],
    coefs=[1.0, -2.0],
    rhs=5.0,
    sense=CST.LE,
    name='MyOptimalityCut'
)

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.

It must be LE, GE, or EQ.

name¶: The name for the cut.

class FeasibilityCut(vars, coefs, rhs, sense, name='FC')[source]¶

Bases: Cut

The class of feasibility cuts in Benders decomposition.

Parameters:

vars (list[str]) – A list of variable names involved in the cut.
coefs (list[float | int]) – A list of coefficients corresponding to the variables in the cut.
rhs (float | int) – The right-hand side value of the cut.
sense (str) – The sense of the cut, must be in senses.
name (str) – A name for the cut.

Example

from benderslib import FeasibilityCut, CST

fc = FeasibilityCut(
    vars=['x1', 'x2'],
    coefs=[1.0, -2.0],
    rhs=5.0,
    sense=CST.LE,
    name='MyFeasibilityCut'
)

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.

It must be LE, GE, or EQ.

name¶: The name for the cut.

class CutGenerator(master_problem: MasterProblem, sub_problem: SubProblem | SubProblems, params: BendersParams | None = None)[source]¶

Bases: ABC

The base class for cut generators in Benders decomposition.

Any specific cut generation method (e.g., ClassicalOCGen) should inherit from this class and implement the abstract method generate(). Attributes that will not change during the Benders process should be ideally initialized in __init__ for efficiency.

Parameters:

master_problem (MasterProblem) – An instance of MasterProblem representing the master problem.
sub_problem (SubProblem | SubProblems) – An instance of SubProblem representing the subproblem, or SubProblems for multiple subproblems.
params (BendersParams, optional) – The parameters that can be set by the user (see BendersParams). If not provided, default parameters will be used.

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).

abstractmethod generate() → list[OptimalityCut] | list[FeasibilityCut][source]¶

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

This method generates and returns a list of cuts (either OptimalityCut or FeasibilityCut) with the information from master_problem and sub_problem, which are updated during the Benders solving process.

Example implementations can be found in the source code of ClassicalOCGen and ClassicalFCGen.

Note

Alternatively, BendersLib allows using a lightweight function (instead of the class CutGenerator) as the cut generator. The signature of the function should be as follows.

from benderslib import Cut, OptimalityCut, FeasibilityCut

def cut_generator(master_problem: MasterProblem, sub_problem: SubProblem) -> list[Cut]:
    cuts = []
    cut = Cut(...) # implement the cut generation logic here
    cuts.append(cut)
    return cuts  # a list of OptimalityCut or FeasibilityCut

To maintain state, implement a class inherited from CutGenerator instead.

Master and Sub Problem¶

class ProblemBase(solver_backend: SolverBase)[source]¶

Bases: object

The base class for MasterProblem and SubProblem in Benders decomposition.

Parameters:

solver_backend (SolverBase) – An instance of a solver backend (e.g., Gurobi) that implements the SolverBase interface.
complicating_vars (list, optional) – A list of names of the complicating variables.

solver: SolverBase¶: An instance of the solver backend (see classes in Solver Interfaces).

model¶

A copy of the original solver model instance.

This attribute is exactly the solver-specific model instance passed during initialization. It allows direct access to solver-specific features (attributes and methods) not covered by the abstract interface. Refer to Supported Solvers’ Features for supported solvers, and their documentation.

status¶: The status of the problem (see BendersConsts for possible values).

add_estimators(estimators: list[str], prob: list[float] = None, lb: float = 0) → None[source]¶

Add estimator variable(s) to the objective function of the model.

Parameters:

estimators (list[str]) – A list of names for the estimator variables to be added.
prob (list[float]) – A list of probabilities (weights) associated with each estimator variable. The length of prob should match that of estimators. If None, equal weights are assigned to all estimator variables. Note that the sum of probabilities does not need to equal 1.
lb (float) – The lower bound for the estimator variables. Default is 0.0.

Example

# Adding multiple estimators with specified probabilities
solver.add_estimators(
    estimators=['theta1', 'theta2'],
    prob=[0.3, 0.7],
    lb=0.0
)

# Adding a single estimator
solver.add_estimators(['theta'])

fix_vars(var_values: dict[str, float]) → None[source]¶

Fix the values of specified variables in the model.

Parameters:: var_values (dict[str, float]) – A dictionary mapping variable names to their fixed values.

Example

problem.fix_vars({'x1': 10, 'x2': 5.5})

unfix_vars(vars: list[str]) → None[source]¶

Unfix the specified variables in the model by restoring their original bounds.

Parameters:: vars (list) – A list of variable names to be unfixed.

Example

problem.unfix_vars(['x1', 'x2'])

get_var_values(vars: list[str] | None = None) → dict[str, float][source]¶

Get the current values of specified variables in the model.

Parameters:: vars (list[str] or None) – A list of variable names to retrieve values for. If None, retrieves values for all variables
Returns:: A dictionary mapping variable names to their current values.
Return type:: dict[str, float]

Example

values = problem.get_var_values(['x1', 'x2'])
# or get all variable values
all_values = problem.get_var_values()

get_var_coefs(vars: list[str] | None = None) → dict[str, list][source]¶

Get the coefficients of specified variables in all the constraints of the model.

Parameters:: vars (list[str] or None) – A list of variable names to retrieve coefficients for. If None, retrieves coefficients for all variables.
Returns:: A dictionary mapping variable names to a list of their coefficients in each constraint.
Return type:: dict[str, list]

Example

coefs = problem.get_var_coefs(['x1', 'x2'])
# or get coefficients for all variables
all_coefs = problem.get_var_coefs()

get_rhs() → list[float][source]¶

Get the right-hand side values of all constraints in the model.

Returns:: A list of right-hand side values for each constraint.
Return type:: list[float]

Example

rhs = problem.get_rhs()

get_dual_values() → list[float][source]¶

Get the dual values (shadow prices) of all constraints in the model. This is essential for generating Classical Benders optimality cuts, which are used by ClassicalBenders.

Returns:: A list of dual values for each constraint.
Return type:: list[float]

Example

pi = problem.get_dual_values()

get_extreme_ray() → list[float][source]¶

Get the extreme ray of the model. This is essential for generating Classical Benders feasibility cuts, which are used by ClassicalBenders.

Returns:: A list representing the extreme ray.
Return type:: list[float]

Example

ray = problem.get_extreme_ray()

get_obj() → float[source]¶

Get the objective value of the model after solving.

Returns:: The objective value.
Return type:: float

Example

obj_val = problem.get_obj()

solve() → None[source]¶: Solve the problem and update the status attribute.

compute_iis() → set[str][source]¶

Compute the Irreducible Infeasible Subsystem (IIS) of the model if it is infeasible.

This method can be useful for Combinatorial Benders Decomposition to identify a set of conflicting (binary) variables that causing subproblem infeasibility. This set of variables can be smaller than the full set of complicating variables, thus potentially leading to stronger NoGoodFC.

Caution

IIS is not guaranteed to be unique.

Returns:: A list of variable names involved in the IIS.
Return type:: list[str]

Example

iis_vars = sub_problem.compute_iis()

class MasterProblem(solver_backend: SolverBase, complicating_vars: list = None, params: BendersParams | None = None)[source]¶

Bases: ProblemBase

The master problem in Benders decomposition.

Parameters:

solver_backend (SolverBase) – An instance of a solver backend (e.g., Gurobi) that implements the SolverBase interface.
complicating_vars (list, optional) – A list of names of the complicating variables.
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 MasterProblem
from benderslib.solvers import Gurobi

model = ...  # Define your master problem model here
solver_backend = Gurobi(model)
master_problem = MasterProblem(solver_backend)

complicating_vars¶: A list of names of the complicating variables.

optimality_cuts: set[Cut]¶: A set of optimality cuts added to the master problem.

feasibility_cuts: set[Cut]¶: A set of feasibility cuts added to the master problem.

cuts: dict[str, Cut]¶: A dictionary mapping cut names to their corresponding instances.

estimators: list[str]¶: A list of estimator variable names added to the master problem.

params: BendersParams | None¶: The parameters that can be set by the user (see BendersParams).

get_estimator_values() → dict[str, float][source]¶

Get the current values of the estimator variables in the master problem.

Returns:: A dictionary mapping estimator variable names to their current values.
Return type:: dict[str, float]

add_cut(cut) → str | None[source]¶

Add a Benders cut to the master problem.

Parameters:: cut (Cut) – An instance of Cut, either an OptimalityCut or FeasibilityCut.
Returns:: The name of the added cut in the master problem.
Return type:: str

remove_cut(cut_name: str) → None[source]¶

Remove a cut from the master problem by its name.

Parameters:: cut_name (str) – The name of the constraint to be removed.

Example

problem.remove_cut('BendersOC_1')

add_estimators(estimators: list[str], prob: list[float] = None, lb: float = 0) → None¶

Add estimator variable(s) to the objective function of the model.

Parameters:

estimators (list[str]) – A list of names for the estimator variables to be added.
prob (list[float]) – A list of probabilities (weights) associated with each estimator variable. The length of prob should match that of estimators. If None, equal weights are assigned to all estimator variables. Note that the sum of probabilities does not need to equal 1.
lb (float) – The lower bound for the estimator variables. Default is 0.0.

Example

# Adding multiple estimators with specified probabilities
solver.add_estimators(
    estimators=['theta1', 'theta2'],
    prob=[0.3, 0.7],
    lb=0.0
)

# Adding a single estimator
solver.add_estimators(['theta'])

compute_iis() → set[str]¶

Compute the Irreducible Infeasible Subsystem (IIS) of the model if it is infeasible.

Caution

IIS is not guaranteed to be unique.

Returns:: A list of variable names involved in the IIS.
Return type:: list[str]

Example

iis_vars = sub_problem.compute_iis()

fix_vars(var_values: dict[str, float]) → None¶

Fix the values of specified variables in the model.

Parameters:: var_values (dict[str, float]) – A dictionary mapping variable names to their fixed values.

Example

problem.fix_vars({'x1': 10, 'x2': 5.5})

get_dual_values() → list[float]¶

Get the dual values (shadow prices) of all constraints in the model. This is essential for generating Classical Benders optimality cuts, which are used by ClassicalBenders.

Returns:: A list of dual values for each constraint.
Return type:: list[float]

Example

pi = problem.get_dual_values()

get_extreme_ray() → list[float]¶

Get the extreme ray of the model. This is essential for generating Classical Benders feasibility cuts, which are used by ClassicalBenders.

Returns:: A list representing the extreme ray.
Return type:: list[float]

Example

ray = problem.get_extreme_ray()

get_obj() → float¶

Get the objective value of the model after solving.

Returns:: The objective value.
Return type:: float

Example

obj_val = problem.get_obj()

get_rhs() → list[float]¶

Get the right-hand side values of all constraints in the model.

Returns:: A list of right-hand side values for each constraint.
Return type:: list[float]

Example

rhs = problem.get_rhs()

get_var_coefs(vars: list[str] | None = None) → dict[str, list]¶

Get the coefficients of specified variables in all the constraints of the model.

Parameters:: vars (list[str] or None) – A list of variable names to retrieve coefficients for. If None, retrieves coefficients for all variables.
Returns:: A dictionary mapping variable names to a list of their coefficients in each constraint.
Return type:: dict[str, list]

Example

coefs = problem.get_var_coefs(['x1', 'x2'])
# or get coefficients for all variables
all_coefs = problem.get_var_coefs()

get_var_values(vars: list[str] | None = None) → dict[str, float]¶

Get the current values of specified variables in the model.

Parameters:: vars (list[str] or None) – A list of variable names to retrieve values for. If None, retrieves values for all variables
Returns:: A dictionary mapping variable names to their current values.
Return type:: dict[str, float]

Example

values = problem.get_var_values(['x1', 'x2'])
# or get all variable values
all_values = problem.get_var_values()

solve() → None¶: Solve the problem and update the status attribute.

unfix_vars(vars: list[str]) → None¶

Unfix the specified variables in the model by restoring their original bounds.

Parameters:: vars (list) – A list of variable names to be unfixed.

Example

problem.unfix_vars(['x1', 'x2'])

solver: SolverBase¶: An instance of the solver backend (see classes in Solver Interfaces).

model¶

A copy of the original solver model instance.

status¶: The status of the problem (see BendersConsts for possible values).

class SubProblem(solver_backend: SolverBase, complicating_vars: list = None, params: BendersParams | None = None)[source]¶

Bases: ProblemBase

The sub problem in Benders decomposition.

Parameters:

solver_backend (SolverBase) – An instance of a solver backend (e.g., Gurobi) that implements the SolverBase interface.
complicating_vars (list, optional) – A list of names of the complicating variables.
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 SubProblem
from benderslib.solvers import Gurobi

model = ...  # Define your sub problem model here
solver_backend = Gurobi(model)
sub_problem = SubProblem(solver_backend)

complicating_vars¶: A list of names of the complicating variables.

params¶: The parameters that can be set by the user (see BendersParams).

add_estimators(estimators: list[str], prob: list[float] = None, lb: float = 0) → None¶

Add estimator variable(s) to the objective function of the model.

Parameters:

estimators (list[str]) – A list of names for the estimator variables to be added.
prob (list[float]) – A list of probabilities (weights) associated with each estimator variable. The length of prob should match that of estimators. If None, equal weights are assigned to all estimator variables. Note that the sum of probabilities does not need to equal 1.
lb (float) – The lower bound for the estimator variables. Default is 0.0.

Example

# Adding multiple estimators with specified probabilities
solver.add_estimators(
    estimators=['theta1', 'theta2'],
    prob=[0.3, 0.7],
    lb=0.0
)

# Adding a single estimator
solver.add_estimators(['theta'])

compute_iis() → set[str]¶

Compute the Irreducible Infeasible Subsystem (IIS) of the model if it is infeasible.

Caution

IIS is not guaranteed to be unique.

Returns:: A list of variable names involved in the IIS.
Return type:: list[str]

Example

iis_vars = sub_problem.compute_iis()

fix_vars(var_values: dict[str, float]) → None¶

Fix the values of specified variables in the model.

Parameters:: var_values (dict[str, float]) – A dictionary mapping variable names to their fixed values.

Example

problem.fix_vars({'x1': 10, 'x2': 5.5})

get_dual_values() → list[float]¶

Get the dual values (shadow prices) of all constraints in the model. This is essential for generating Classical Benders optimality cuts, which are used by ClassicalBenders.

Returns:: A list of dual values for each constraint.
Return type:: list[float]

Example

pi = problem.get_dual_values()

get_extreme_ray() → list[float]¶

Get the extreme ray of the model. This is essential for generating Classical Benders feasibility cuts, which are used by ClassicalBenders.

Returns:: A list representing the extreme ray.
Return type:: list[float]

Example

ray = problem.get_extreme_ray()

get_obj() → float¶

Get the objective value of the model after solving.

Returns:: The objective value.
Return type:: float

Example

obj_val = problem.get_obj()

get_rhs() → list[float]¶

Get the right-hand side values of all constraints in the model.

Returns:: A list of right-hand side values for each constraint.
Return type:: list[float]

Example

rhs = problem.get_rhs()

get_var_coefs(vars: list[str] | None = None) → dict[str, list]¶

Get the coefficients of specified variables in all the constraints of the model.

Parameters:: vars (list[str] or None) – A list of variable names to retrieve coefficients for. If None, retrieves coefficients for all variables.
Returns:: A dictionary mapping variable names to a list of their coefficients in each constraint.
Return type:: dict[str, list]

Example

coefs = problem.get_var_coefs(['x1', 'x2'])
# or get coefficients for all variables
all_coefs = problem.get_var_coefs()

get_var_values(vars: list[str] | None = None) → dict[str, float]¶

Get the current values of specified variables in the model.

Parameters:: vars (list[str] or None) – A list of variable names to retrieve values for. If None, retrieves values for all variables
Returns:: A dictionary mapping variable names to their current values.
Return type:: dict[str, float]

Example

values = problem.get_var_values(['x1', 'x2'])
# or get all variable values
all_values = problem.get_var_values()

solve() → None¶: Solve the problem and update the status attribute.

unfix_vars(vars: list[str]) → None¶

Unfix the specified variables in the model by restoring their original bounds.

Parameters:: vars (list) – A list of variable names to be unfixed.

Example

problem.unfix_vars(['x1', 'x2'])

solver: SolverBase¶: An instance of the solver backend (see classes in Solver Interfaces).

model¶

A copy of the original solver model instance.

status¶: The status of the problem (see BendersConsts for possible values).

class SubProblems(sub_problems: Iterable, prob: list[float] | None = None, params: BendersParams | None = None)[source]¶

Bases: object

A collection of multiple subproblems in Benders decomposition for stochastic programming.

Parameters:

sub_problems (list[SubProblem | LogicBasedSubProblem]) – A list of SubProblem or LogicBasedSubProblem instances.
prob (list[float], optional) – A list of probabilities (weights) associated with each subproblem. The length of prob should match that of sub_problems. If None, equal weights are assigned to all subproblems.
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 SubProblems, SubProblem
from benderslib.solvers import Gurobi

model1 = ...  # Define the first subproblem model
model2 = ...  # Define the second subproblem model
solver_backend1 = Gurobi(model1)
solver_backend2 = Gurobi(model2)

sub1 = SubProblem(Gurobi(model1))
sub2 = SubProblem(Gurobi(model2))
sub_problems = SubProblems([sub1, sub2], prob=[0.4, 0.6])

sub_problems¶: A list of SubProblem or LogicBasedSubProblem instances.

prob¶

A list of probabilities or weights associated with each subproblem.

If None, equal weights are assumed.

params: BendersParams | None¶: The parameters that can be set by the user (see BendersParams).

status¶: The status of the problem (see BendersConsts for possible values).

get_obj() → float[source]¶

Get the prob weighted objective value of all subproblems.

It is used by the solve() method.

Returns:: The weighted objective value.
Return type:: float

Example

obj_val = sub_problems.get_obj()

fix_vars(var_values: dict[str, float]) → None[source]¶

Fix the values of specified variables in all subproblems.

It is used by the solve() method.

Parameters:: var_values (dict[str, float]) – A dictionary mapping variable names to their fixed values.

Example

sub_problems.fix_vars({'x1': 10, 'x2': 5.5})

get_var_values(vars: list[str] = None) → dict[int, dict[str, float]][source]¶

Get the current values of specified variables in all subproblems.

It is used by the solve() method.

Parameters:: vars (list[str], optional) – A list of variable names to retrieve values for. If None, retrieves values for all variables.
Returns:: A dictionary mapping subproblem indices to dictionaries of variable names and their current values.
Return type:: dict[int, dict[str, float]]

Example

values = sub_problems.get_var_values(['x1', 'x2'])
# or get all variable values
all_values = sub_problems.get_var_values()

solve() → None[source]¶

Solve all subproblems and update the status attribute.

If any subproblem is infeasible and BendersParams.multi_feas_cut is False, the solving process will stop early.

It is used by the solve() method.

prl_solve() → None[source]¶

Solve all subproblems in parallel and update the status attribute.

If any subproblem is infeasible and BendersParams.multi_feas_cut is False, the solving process will stop early.

It is used by the solve() method.

class LogicBasedSubProblem(complicating_vars: list[str], params: BendersParams | None = None)[source]¶

Bases: ABC

The abstract base class for the subproblem in the Logic-based Benders Decomposition.

To implement a customized subproblem, at least solve() required to be overridden, as it will be called during the Benders solving process after solve() is invoked. Other methods and attributes can be added as needed, based on the specific implementation of CutGenerator.

Parameters:

complicating_vars (list[str]) – A list of names of the complicating variables.
params (BendersParams, optional) – The parameters that can be set by the user (see BendersParams). If not provided, default parameters will be used.

complicating_vars: list[str]¶

A list of names of the complicating variables.

Example

complicating_vars = ['x1', 'x2', 'x3']

complicating_var_values: dict[str, float | int]¶

The values of complicating variables provided by the master problem.

After calling solve(), this attribute will be updated via fix_vars() after the master problem is solved. Therefore, users do not need to set it manually, and can directly use it when implementing solve().

Example

complicating_var_values = {'x1': 10, 'x2': 5.5, 'x3': 0}

obj: float | int | None¶: The objective value of the subproblem after solving.

var_values: dict[str, float | int]¶: The values of variables in the subproblem after solving.

status¶: The status of the problem (see BendersConsts for possible values).

params: BendersParams | None¶: The parameters that can be set by the user (see BendersParams).

abstractmethod solve() → None[source]¶

Solve the subproblem and update the status, obj, and var_values attributes.

This method is required to be implemented.

status is used in the solve() method to indicate if the subproblem is optimal (OPTIMAL) or infeasible (INFEASIBLE), guiding whether to add optimality or feasibility cuts.
obj is used in the solve() method to compute the upper bound, determining convergence.
var_values is used in the solve() method when saving the final solution.

Caution

It is safe to assume that complicating_var_values has been set.
Always update status, obj, and var_values after solving the subproblem. Returning values from this method will be ignored.

Example

from benderslib import LogicBasedSubProblem, CST

class MyCustomSubproblem(LogicBasedSubProblem):
    def solve(self):
        # Access master variables' values
        x_val = self.complicating_var_values['x']

        # Implement your custom solving logic here
        # and set the status, obj, and var_values attributes
        if x_val > 5:
            self.status = CST.INFEASIBLE
            self.obj = None
            self.var_values = {}
        else:
            self.status = CST.OPTIMAL
            self.obj = 10 - x_val
            self.var_values = {'y': 2 * x_val}

custom_subproblem = MyCustomSubproblem(complicating_vars=['x'])

Note

Alternatively, BendersLib allows using a lightweight function (instead of the class LogicBasedSubProblem) as the subproblem solver. The signature of the function should be as follows.

from benderslib import CST

def subproblem_solver(master_vars: dict[str, float]) -> tuple[str, float, dict[str, float]]:
    # Access master variables' values
    x_val = master_vars['x']

    # Implement your custom solving logic here
    if x_val > 5:
        status = CST.INFEASIBLE
        obj = None
        var_values = {}
    else:
        status = CST.OPTIMAL
        obj = 10 - x_val
        var_values = {'y': 2 * x_val}

    # Return status, objective value, and variable values (as a dict)
    return status, obj, var_values

To maintain state, implement a class inherited from LogicBasedSubProblem instead.

Benders Algorithm¶

class BendersSolver(master_problem: MasterProblem, sub_problem: SubProblem | SubProblems, complicating_vars: list[str], optimality_cut=None, feasibility_cut=None, params: BendersParams | None = None)[source]¶

Bases: object

The core class for Benders decomposition methods.

Any specific Benders decomposition method (e.g., ClassicalBenders) is inherited from this class.

Parameters:

master_problem (MasterProblem) – An instance of MasterProblem representing the master problem.
sub_problem (SubProblem | SubProblems) – An instance of SubProblem representing the subproblem, or SubProblems for multiple subproblems.
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.
params (BendersParams, optional) – The parameters that can be set by the user (see BendersParams). If not provided, default parameters will be used.

Caution

The optimality_cut parameter requires the CutGenerator’s subclass itself, not an instance. For example, use ClassicalOC, not ClassicalOC(). This also applies to the feasibility_cut parameter.

from benderslib import ClassicalBenders, ClassicalOCGen, ClassicalFCGen

BD = ClassicalBenders(mp, sp, com_vars, optimality_cut=ClassicalOC, feasibility_cut=ClassicalFC)

# Wrong
# BD = ClassicalBenders(mp, sp, com_vars, optimality_cut=ClassicalOC(), feasibility_cut=ClassicalFC())

master_problem¶: An instance of MasterProblem representing the master problem.

sub_problem¶: An instance of SubProblem or SubProblems representing the subproblem(s).

complicating_vars¶: A list of names of the complicating variables.

optimality_cut¶: An instance of CutGenerator for generating optimality cuts.

feasibility_cut¶: An instance of CutGenerator for generating feasibility cuts.

params¶: The parameters that can be set by the user (see BendersParams).

result¶: An instance of BendersResult that stores the results and statistics.

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)[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
)

solve() → None[source]¶

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.

bnc_solve()[source]¶

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[source]¶

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[source]¶

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.