Data Classes

Parameters

class BendersParams(theta_lb: float = 0.0, tol_obj_diff: float = 1e-06, tol_cut_diff: float = 1e-08, cut_normalize: bool = False, cut_max_norm: float = 100000.0, tol_abs: float = 1e-06, tol_rel: float = 0.0001, time_limit: float = inf, iter_limit: int = inf, multi_opti_cut: bool = False, multi_feas_cut: bool = False, parallel_sub: bool = False, parallel_threads: int = -1, use_iis_cut: bool = False, use_bnc: bool = False, bnc_frac_sol: bool = False, log_freq_sec: float = 0.5, log_freq_iter: int = 1, log_level: str = 'INFO', log_to_console: bool = True, log_file: str = None)

Parameters for BendersLib that can be manipulated by the users.

A BendersParams instance is passed to the Benders algorithm during its initialization. The users may initialize a BendersParams instance with customized parameters and then pass it to the Benders algorithm. Parameters that are not specified will take their default values.

Example

# Initialize with customized parameters
params = BendersParams(tol_abs=1e-5, time_limit=3600)

# Or, using a dictionary
# params = BendersParams(**{'tol_abs': 1e-5, 'time_limit': 3600})

# Or, using default parameters
# params = BendersParams()

BD = ClassicalBenders(mp, sp, complicating_vars, params=params)

theta_lb: float = 0.0

Lower bound for the estimator variable in the master problem.

The default value of 0.0 is suitable for subproblems with non-negative objective values. For problems where the subproblem’s objective value can be negative, you need to adjust this parameter to ensure the Benders algorithm converges correctly.

Ideally, this value should be as large as possible while still being a valid lower bound for the subproblem’s objective value, to provide a tighter approximation in the master problem and potentially improve convergence. For example, you can get a valid lower bound by solving the linear relaxation of the subproblem if it contains integer variables. In stochastic programming, you can solve the subproblem of each scenario independently without fixing the complicating variables to get a valid lower bound.

tol_obj_diff: float = 1e-06

Tolerance for estimator values and subproblem objective values comparison.

When generating optimality cuts, the cut is added only if sub_obj - theta > tol_obj_diff, to avoid numerical issues. It is set to be equal to tol_abs by default.

tol_cut_diff: float = 1e-08

Tolerance for cut coefficients and RHS comparison.

When adding a cut, if all coefficients and right-hand side (RHS) differ from an existing cut by no more than tol_cut_diff, the new cut is considered duplicate and will not be added.

cut_normalize: bool = False

Whether to normalize the cut coefficients and right-hand side (RHS) when adding a cut.

If True, the cut coefficients and RHS are normalized to have an L2 norm of at most cut_max_norm before being added to the master problem. This can help improve numerical stability in the master problem solver, especially when the cut coefficients have large magnitudes. If False, the cut coefficients and RHS are not normalized, and are added to the master problem as they are generated.

cut_max_norm: float = 100000.0

The maximum allowed L2 norm for the cuts’ coefficients when normalizing cuts.

This parameter is used when cut_normalize is True. When normalizing a cut, if the L2 norm of the cut’s coefficient vector exceeds this threshold, the coefficients and right-hand side (RHS) of the cut are scaled down to have an L2 norm equal to this threshold; otherwise, the cut is not modified.

tol_abs: float = 1e-06

Absolute tolerance for convergence, terminate when abs(UB - LB) <= tol_abs.

tol_rel: float = 0.0001

Relative tolerance for convergence, terminate when abs(UB - LB) / abs(UB) <= tol_rel.

time_limit: float = inf

Time limit for the Benders algorithm in seconds.

iter_limit: int = inf

Iteration limit for the Benders algorithm.

multi_opti_cut: bool = False

[L-shaped method] Whether to add multiple optimality cuts per scenario in the L-shaped method.

If True, estimator variables are added to the master problem for each scenario, and an optimality cut is added for each scenario in each iteration; If False, only one estimator variable is added to the master problem, and an aggregated optimality cut is added. One need to trade-off between the size of the master problem and the number of iterations when deciding whether to use multiple optimality cuts.

multi_feas_cut: bool = False

[L-shaped method] Whether to add multiple feasibility cuts per scenario in the L-shaped method.

If True, all extreme rays are used to generate multiple feasibility cuts; If False, one feasibility cut is added when a infeasible subproblem is found, and the subsequent subproblems will not be solved.

parallel_sub: bool = False

[L-shaped method] Whether to solve subproblems in parallel in the L-shaped method.

If True, the subproblems in a SubProblems instance are solved in parallel; If False, the subproblems are solved sequentially. Note that parallelizing subproblems may lead to faster convergence in some problems, but may not always be beneficial. You should consider the size of the problem, the number of scenarios, and the available computational resources when deciding whether to use parallelization.

parallel_threads: int = -1

[L-shaped method] Number of threads to use for parallel subproblem solving.

This parameter is used when parallel_sub is True. If set to a positive integer, it specifies the number of threads to use for parallel subproblem solving. If set to -1, BendersLib will determine the number of threads to use based on the available CPU cores.

use_iis_cut: bool = False

[Combinatorial Benders] Whether to use IIS-based feasibility cuts.

If True, before generating feasibility cuts, the IIS of the infeasible subproblem is computed, and only the variables in the IIS are used to generate the feasibility cuts. If False, all complicating variables are used to generate the feasibility cuts.

IIS-based cuts require additional computational time to compute the IIS, but may lead to faster convergence in some problems.

You should ensure that the solver used for the subproblem supports IIS computation, see Supported Solvers’ Features.

use_bnc: bool = False

[Branch-and-check] Whether to use the Branch-and-check (Branch-and-Benders-cut) method.

If True, the Benders cut are added as lazy constraints during the branch-and-bound process of the master problem, instead of being added after solving the master problem to optimality. If False, the classical implementation is used, where the master problem is solved to optimality before adding Benders cuts.

Setting use_bnc = True and calling BendersSolver.solve() is equivalent to using BendersSolver.bnc_solve() directly.

bnc_frac_sol: bool = False

[Branch-and-check] Whether to use fractional solutions to generate Benders cuts in the Branch-and-check method.

If True, Benders cuts are generated from fractional solutions of the master problem. If False, Benders cuts are generated only from integer feasible solutions of the master problem. If you implement callbacks with where being NODE, this parameter is required to be True, since the solutions at the nodes can be fractional. Otherwise no cuts will be generated at the nodes, and the callback implemented will not work.

Danger

This feature is experimentally supported only in Copt, Cplex, and Gurobi.

log_freq_sec: float = 0.5

Frequency (in seconds) to log messages to the console/file.

log_freq_iter: int = 1

Frequency (in iterations) to log messages to the console/file.

log_level: str = 'INFO'

Logging level can be DEBUG, INFO, WARNING, ERROR. See Python’s logging levels for details.

log_to_console: bool = True

Whether to print log messages to the console.

log_file: str = None

File path to save log messages. If None, logs are not saved to a file.

Results and Statistics

class BendersResult(lb: float = -inf, lb_list: list = <factory>, ub: float = inf, ub_list: list = <factory>, obj: float = inf, obj_list: list = <factory>, gap_abs: float = inf, gap: float = inf, n_sol: int = 0, n_iter: int = 0, runtime: float = 0.0, runtime_master: float = 0.0, runtime_sub: float = 0.0, n_opt_cuts: int = 0, n_feas_cuts: int = 0, n_cuts: int = 0, solution: dict = <factory>)

Bases: object

Results and statistics from the Benders Decomposition process.

Example

BD = BendersSolver(...)
BD.solve()
print(BD.result.obj)

lb: float = -inf

Lower bound on the objective value.

lb_list: list

List of lower bounds over iterations.

ub: float = inf

Upper bound on the objective value.

ub_list: list

List of upper bounds over iterations.

obj: float = inf

Best objective value found.

obj_list: list

List of objective values of incumbent solutions found over iterations.

gap_abs: float = inf

Absolute gap between upper and lower bounds, defined as abs(ub - lb).

gap: float = inf

Relative gap between upper and lower bounds, defined as abs(ub - lb) / abs(ub).

n_sol: int = 0

Number of feasible solutions found.

n_iter: int = 0

Number of Benders iterations performed.

runtime: float = 0.0

Total runtime of the Benders decomposition process.

runtime_master: float = 0.0

Total runtime spent solving the master problem.

runtime_sub: float = 0.0

Total runtime spent solving the subproblem.

n_opt_cuts: int = 0

Number of optimality cuts added.

n_feas_cuts: int = 0

Number of feasibility cuts added.

n_cuts: int = 0

Total number of optimality cuts and feasibility cuts added.

status = 'UNSOLVED'

Final status of the Benders decomposition process, see BendersConsts for possible values.

solution: dict

Dictionary of variable names to their values in the best solution found.

save(filename: str) → None

Save the result to a JSON file.

Parameters:

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

Constants

class BendersConsts

Immutable constants used in BendersLib.

The constants can be used like CST.OPTIMAL, where CST is a global alias for BendersConsts.

Example

from benderslib import CST

if BD.result.status == CST.OPTIMAL:
    print("Benders algorithm found an optimal solution.")

UNSOLVED = 'UNSOLVED'

Status indicating the problem has not been solved yet.

FEASIBLE = 'FEASIBLE'

Status indicating at least one feasible solution has been found.

OPTIMAL = 'OPTIMAL'

Status indicating an optimal (within tolerances) solution has been found.

INFEASIBLE = 'INFEASIBLE'

Status indicating the problem is infeasible.

UNBOUNDED = 'UNBOUNDED'

Status indicating the problem is unbounded.

TIMEOUT = 'TIMEOUT'

Status indicating the solver reached the time limit.

UNKNOWN = 'UNKNOWN'

Status indicating an unknown solver backend status.

ERROR = 'ERROR'

Status indicating an error occurred during solving.

TERMINATED = 'TERMINATED'

Status indicating the solving process was terminated by the user.

PROCEED = 'PROCEED'

Action in a callback function to continue the Benders algorithm.

TERMINATE = 'TERMINATE'

Action in a callback function to terminate the Benders algorithm.

INCUMBENT = 'INCUMBENT'

Identifier for the Branch-and-check callback trigger location.

NODE = 'NODE'

Identifier for the Branch-and-check callback trigger location.

ESTIMATOR_NAME = 'theta'

Name of the estimator variable in the master problem.

ESTIMATOR_FORMAT = 'theta_{}'

Format string for naming estimator variables with indices.

BINARY = 'B'

Identifier for binary variable type.

INTEGER = 'I'

Identifier for integer variable type.

CONTINUOUS = 'C'

Identifier for continuous variable type.

OPTIMALITY = 'OPTIMALITY'

Type identifier for optimality cuts.

FEASIBILITY = 'FEASIBILITY'

Type identifier for feasibility cuts.

LE = '<='

Less than or equal to cut sense.

GE = '>='

Greater than or equal to cut sense.

EQ = '=='

Equal to cut sense.

MIN = 'MIN'

Identifier for minimization objective sense.

MAX = 'MAX'

Identifier for maximization objective sense.

LOG_NAME_WIDTH = 25

For formatting log before and after iterations.

LOG_ITER_WIDTH = 12

For formatting log during iterations.