Benders Cuts¶

class ClassicalOC(vars: list[str], var_coefs: dict, dual_values: list, rhs: list, estimator='theta')[source]¶

Bases: OptimalityCut

The optimality cut for Classical Benders Decomposition.

The cut uses the optimal dual solution to form a valid lower bound on the subproblem’s cost, represented by the variable \(\eta\) in the master problem.

\[\eta \geq \bar{\pi}^T (b - A x)\]

In this cut, \(\eta\) is the variable representing the subproblem’s cost, \(\bar{\pi}\) is the optimal solution to the dual subproblem (dual values of primal constraints), \(A\) and \(b\) are the matrices that define the subproblem constraints, and \(x\) are the complicating variables. This cut can be interpreted as a first-order Taylor approximation or a supporting hyperplane for the value function of the subproblem.

Parameters:

vars (list[str]) – A list of complicating variable names.
var_coefs (dict) – A dictionary mapping complicating variable names to their coefficients in the subproblem constraints.
dual_values (list) – A list of dual variable values obtained from solving the subproblem.
rhs (list) – A list of right-hand side values of the subproblem constraints.
estimator (str, optional) – The name of the master problem variable representing the subproblem’s cost.

Example

from benderslib import ClassicalOC

# Assuming we have the following data from the subproblem
vars = ['x1', 'x2']         # Complicating variables
var_coefs = {
    'x1': [2, 3],           # Coefficients of x1 in subproblem constraints
    'x2': [1, 4],           # Coefficients of x2 in subproblem constraints
}
dual_values = [0.5, 1.0]    # Optimal dual values from the subproblem
rhs = [10, 20]              # Right-hand side values of the subproblem constraints

# Create the optimality cut
cut = ClassicalOC(vars, var_coefs, dual_values, rhs)

class ClassicalFC(vars: list[str], var_coefs: dict, extreme_ray: list, rhs: list)[source]¶

Bases: FeasibilityCut

The feasibility cut for Classical Benders Decomposition.

The cut is derived from an extreme ray of the subproblem, which acts as a certificate of infeasibility. It is defined as follows to cut off the region of master solutions that leads to this infeasibility.

\[0 \geq \bar{r}^T (b - A x)\]

where \(\bar{r}\) is an extreme ray of the dual subproblem, \(A\) and \(b\) are the matrices that define the subproblem constraints, and \(x\) are the complicating variables. This cut is a direct application of Farkas’ Lemma. The extreme ray \(\bar{r}\) is typically provided by the LP solver when it determines the primal subproblem is infeasible (and thus the dual is unbounded). It informs the master problem that any future choice of \(x\) violating this constraint will also result in an infeasible subproblem.

Parameters:

vars (list[str]) – A list of complicating variable names.
var_coefs (dict) – A dictionary mapping complicating variable names to their coefficients in the subproblem constraints.
extreme_ray (list) – A list representing an extreme ray of the subproblem’s feasible region.
rhs (list) – A list of right-hand side values of the subproblem constraints.

Example

from benderslib import ClassicalFC

# Assuming we have the following data from the subproblem
vars = ['x1', 'x2']         # Complicating variables
var_coefs = {
    'x1': [2, 3],           # Coefficients of x1 in subproblem constraints
    'x2': [1, 4],           # Coefficients of x2 in subproblem constraints
}
extreme_ray = [1.0, 0.5]    # Extreme ray from the dual subproblem
rhs = [10, 20]              # Right-hand side values of the subproblem constraints

# Create the feasibility cut
cut = ClassicalFC(vars, var_coefs, extreme_ray, rhs)

class NoGoodFC(bin_var_values: dict)[source]¶

Bases: FeasibilityCut

The feasibility cut for Combinatorial Benders Decomposition.

It is defined as follows to ensure at least one binary variable changes its value in the next iteration,

\[\sum_{i \in I_1} (1 - x_i) + \sum_{i \in I_0} x_i \geq 1\]

where \(I_1\) is the set of indices of binary variables that are 1 in the current solution, and \(I_0\) is the set of indices of binary variables that are 0 in the current solution. It can be rewritten as follows.

\[\sum_{i \in I_1} x_i - \sum_{i \in I_0} x_i \leq |I_1| - 1\]

These two forms can both be found in the literature. To make sure the cut is strong, \(|I_1 \cup I_0|\) should be as small as possible, i.e., only including the binary variables that are relevant to the infeasibility of the subproblem, which is usually a small subset of all binary variables in the master problem.

Parameters:: bin_var_values (dict) – A dictionary mapping binary variable names to their values in the current master problem solution.

Example

from benderslib import NoGoodFC

# Assuming we have the following binary variable values from the master problem
bin_var_values = {
    'x1': 1,  # Binary variable x1 is 1
    'x2': 0,  # Binary variable x2 is 0
    'x3': 1,  # Binary variable x3 is 1
}

# Create the no-good feasibility cut
cut = NoGoodFC(bin_var_values)

Hint

bin_var_values should ideally be a small subset of all binary variables in the master problem, only including those that are relevant to the infeasibility of the subproblem.

class CombinatorialOC(bin_var_values: dict, sub_obj: float, big_m: float = None, estimator: str = 'theta')[source]¶

Bases: OptimalityCut

The optimality cut for Combinatorial Benders Decomposition.

It is defined as follows to lower bound the estimator \(\theta\) for subproblem in the master problem.

\[\theta \geq z^* - M \left( \sum_{i \in I_1} (1 - x_i) + \sum_{i \in I_0} x_i \right)\]

where \(z^*\) is the objective value of the subproblem given the current master problem solution, \(I_1\) is the set of indices of binary variables that are 1 in the current solution, and \(I_0\) is the set of indices of binary variables that are 0 in the current solution, and \(M\) is a large constant. It can be rewritten as follows.

\[\theta - M \sum_{i \in I_1} x_i + M \sum_{i \in I_0} x_i \geq z^* - M |I_1|\]

To ensure validity, \(M\) should be larger than the maximum possible objective value of the subproblem. If it is not specified, BendersLib set \(M = z^* - L\) in each iteration, where \(L = \bar{\theta}\) is a known lower bound on \(\theta\), retrieved from the master problem in the current iteration. The cut is rewritten as follows.

\[\frac{\theta}{z^* - L} - \sum_{i \in I_1} x_i + \sum_{i \in I_0} x_i \geq \frac{z^*}{z^* - L} - |I_1|\]

This form is used when \(z^* - L \neq 0\) to improve the numerical stability.

Parameters:

bin_var_values (dict) – A dictionary mapping binary variable names to their values in the current master problem solution.
sub_obj (float) – The objective value of the subproblem given the current master problem solution.
big_m (float, optional, default=sub_obj) – A large constant used in the cut formulation.
estimator (str, optional) – The name of the master problem variable representing the subproblem’s cost.

Example

from benderslib import CombinatorialOC

# Assuming we have the following binary variable values from the master problem
bin_var_values = {
    'x1': 1,  # Binary variable x1 is 1
    'x2': 0,  # Binary variable x2 is 0
    'x3': 1,  # Binary variable x3 is 1
}
sub_obj = 50  # Objective value of the subproblem given the current master problem solution

# Create the combinatorial optimality cut
cut = CombinatorialOC(bin_var_values, sub_obj)

class LShapedOC(vars: list[str], probs: list[float], duals: list[list[float]], rhss: list[list[float]], var_coefs_list: list[dict], estimator='theta')[source]¶

Bases: OptimalityCut

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

This class encapsulates the aggregation logic. It takes raw data from all scenarios (probabilities, duals, matrices) and computes the final cut. The cut represents the following inequality.

\[\theta \geq \sum_{\omega} p_\omega [\pi_\omega^T (h_\omega - T_\omega x)]\]

Parameters:

vars (list[str]) – A list of variable names for the complicating variables \(x\).
probs (list[float]) – A list of probabilities for each scenario \(p_\omega\).
duals (list[list[float]]) – A list of lists, where each inner list contains the dual variable values \(\pi_\omega^T\) for a scenario.
rhss (list[list[float]]) – A list of lists, where each inner list is the right-hand side \(h_ω\) for a scenario.
var_coefs_list (list[dict]) – A list of dictionaries. Each dictionary maps variable names to their coefficient lists \(T_ω\) for a scenario.
estimator (str, optional) – The name of the master problem variable representing the subproblem’s cost.

Example

from benderslib import LShapedOC

# Assuming we have the following data from multiple scenarios
vars = ['x1', 'x2']     # Complicating variables
probs = [0.5, 0.5]      # Probabilities for each scenario
duals = [               # Dual variable values for each scenario
    [0.5, 1.0],         # Scenario 1 duals
    [0.3, 0.7]          # Scenario 2 duals
]
rhss = [                # Right-hand side (RHS) values for each scenario
    [10, 20],           # Scenario 1 RHS
    [15, 25]            # Scenario 2 RHS
]
var_coefs_list = [      # Coefficient lists for each scenario
    {                   # Scenario 1 coefficients
        'x1': [2, 3],
        'x2': [1, 4]
    },
    {                   # Scenario 2 coefficients
        'x1': [3, 2],
        'x2': [4, 1]
    }
]

# Create the L-shaped optimality cut
cut = LShapedOC(vars, probs, duals, rhss, var_coefs_list)

class GeneralizedOC(vars: list[str], var_values: dict[str, float], var_coefs: dict[str, list[float]], sub_obj: float, multipliers: list[float], estimator='theta')[source]¶

Bases: OptimalityCut

The optimality cut for Generalized Benders Decomposition.

This cut uses the Lagrange multipliers from the subproblem to form a valid lower bound on the subproblem’s cost, represented by the variable \(\eta\) in the master problem. It is assumed that the original problem is linearly separable into master and subproblem components, and the constraints of the master problem are linear. These assumptions are necessary for linear generalized optimality cuts.

\[\eta \geq f_y(\bar{y}) - \bar{\lambda}^T A (x - \bar{x})\]

In this cut, \(\eta\) is the variable representing the subproblem’s cost. \(f_y(\bar{y})\) is the objective value of the subproblem given the current master problem solution \(\bar{x}\). \(\bar{\lambda}\) are the Lagrange multipliers (dual variable values) obtained from solving the subproblem. \(A\) represents the coefficients of complicating variables in the subproblem constraints, and \(x\) are the complicating variables.

Parameters:

vars (list[str]) – A list of complicating variable names.
var_values (dict[str, float]) – A dictionary mapping variable names to their current values in the master problem.
var_coefs (dict[str, list[float]]) – A dictionary mapping complicating variable names to their coefficients in the subproblem constraints.
sub_obj (float) – The objective value of the subproblem given the current master problem solution.
multipliers (list[float]) – A list of Lagrange multipliers (dual variable values) obtained from solving the subproblem.
estimator (str, optional) – The name of the master problem variable representing the subproblem’s cost.

Example

from benderslib import GeneralizedOC

# Assuming we have the following data from the subproblem
vars = ['x1', 'x2']         # Complicating variables
var_values = {              # Current values of complicating variables in the master problem
    'x1': 5,
    'x2': 10
}
var_coefs = {               # Coefficients of complicating variables in subproblem constraints
    'x1': [2, 3],           # Coefficients of x1 in subproblem constraints
    'x2': [1, 4],           # Coefficients of x2 in subproblem constraints
}
sub_obj = 100               # Objective value of the subproblem given the current master problem solution
multipliers = [0.5, 1.0]    # Lagrange multipliers from the subproblem

# Create the generalized optimality cut
cut = GeneralizedOC(vars, var_values, var_coefs, sub_obj, multipliers)

class GeneralizedFC(vars: list[str], var_coefs: dict, extreme_ray: list, rhs: list)[source]¶

Bases: ClassicalFC

The feasibility cut for Generalized Benders Decomposition.

\[0 \geq \bar{r}^T (b - A x)\]

Parameters:

vars (list[str]) – A list of complicating variable names.
var_coefs (dict) – A dictionary mapping complicating variable names to their coefficients in the subproblem constraints.
extreme_ray (list) – A list representing an extreme ray of the subproblem’s feasible region.
rhs (list) – A list of right-hand side values of the subproblem constraints.

Example

from benderslib import GeneralizedFC

# Assuming we have the following data from the subproblem
vars = ['x1', 'x2']         # Complicating variables
var_coefs = {
    'x1': [2, 3],           # Coefficients of x1 in subproblem constraints
    'x2': [1, 4],           # Coefficients of x2 in subproblem constraints
}
extreme_ray = [1.0, 0.5]    # Extreme ray from the dual subproblem
rhs = [10, 20]              # Right-hand side values of the subproblem constraints

# Create the feasibility cut
cut = GeneralizedFC(vars, var_coefs, extreme_ray, rhs)

class GeneLShapedOC(vars: list[str], probs: list[float], var_values: dict[str, float], var_coefs_list: list[dict[str, list[float]]], sub_obj_list: list[float], multipliers_list: list[list[float]], estimator='theta')[source]¶

Bases: OptimalityCut

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

It extends the L-shaped method to handle convex subproblems, acting as a hybrid of GeneralizedOC and LShapedOC. While LShapedOC aggregates cuts from multiple linear subproblems, this class applies the principles of GeneralizedOC (for single convex problems) to a multi-scenario setting.

It constructs a single, aggregated optimality cut by taking a probability-weighted average of the generalized cuts from each convex subproblem. This enables the GeneLShaped method to solve problems with multiple independent convex subproblems (e.g., stochastic programs with convex recourse), extending the capability of the standard LShaped method which is limited to linear subproblems.

The aggregated cut is of the form

\[\theta \geq \sum_{\omega \in \Omega} p_\omega \left( f_\omega(\bar{x}) + \nabla f_\omega(\bar{x})^T (x - \bar{x}) \right)\]

where \(\theta\) is the estimator variable for the total subproblem cost in the master problem. \(\Omega\) is the set of all scenarios. \(p_\omega\) is the probability of scenario \(\omega\). \(f_\omega(\bar{x})\) is the objective value of the subproblem for scenario \(\omega\) at the complicating variable values \(\bar{x}\). \(\nabla f_\omega(\bar{x})\) is the gradient of the subproblem objective function with respect to \(x\), evaluated at \(\bar{x}\). It is computed as \(-\lambda_\omega^T T_\omega\), where \(\lambda_\omega\) are the Lagrange multipliers (duals) and \(T_\omega\) are the coefficients of \(x\) in the subproblem constraints.

Parameters:

vars (list[str]) – A list of complicating variable names (\(x\)).
probs (list[float]) – A list of probabilities (\(p_\omega\)) for each scenario.
var_values (dict[str, float]) – A dictionary mapping complicating variable names to their current values (\(\bar{x}\)).
var_coefs_list (list[dict[str, list[float]]]) – A list of dictionaries, where each dictionary contains the coefficients (\(T_\omega\)) of the complicating variables for a scenario.
sub_obj_list (list[float]) – A list of subproblem objective values (\(f_\omega(\bar{x})\)) for each scenario.
multipliers_list (list[list[float]]) – A list of Lagrange multipliers (\(\lambda_\omega\)) for each scenario’s constraints.
estimator (str, optional) – The name of the master problem variable representing the subproblem’s cost (\(\theta\)).

Example

from benderslib import GeneLShapedOC

# Data from two convex subproblems (scenarios)
complicating_vars = ['x1', 'x2']
master_solution = {'x1': 10, 'x2': 5}
probs = [0.4, 0.6]

# Scenario 1 results
sub_obj_1 = 150.0
var_coefs_1 = {'x1': [2.0, 1.0], 'x2': [1.5, 3.0]}
multipliers_1 = [10.0, 5.0]

# Scenario 2 results
sub_obj_2 = 200.0
var_coefs_2 = {'x1': [2.2, 1.1], 'x2': [1.8, 3.3]}
multipliers_2 = [8.0, 12.0]

# Create the generalized L-shaped optimality cut
cut = GeneLShapedOC(
    vars=complicating_vars,
    probs=probs,
    var_values=master_solution,
    var_coefs_list=[var_coefs_1, var_coefs_2],
    sub_obj_list=[sub_obj_1, sub_obj_2],
    multipliers_list=[multipliers_1, multipliers_2]
)