jijzepttools.modeling.algorithm.benders_decomposition

Benders Decomposition algorithm implementation.

This module provides tools for decomposing mixed-integer programming problems using the Benders decomposition method, which separates binary and continuous variables to solve large-scale optimization problems more efficiently.

The main components are: - extract: Functions to extract variables and constraints - replace: Functions to replace expressions with fixed values or placeholders - generate: Functions to generate master problem, subproblems, and cuts - benders_decomposition: Main algorithm implementation

Submodules

• jijzepttools.modeling.algorithm.benders_decomposition.benders_decomposition
• jijzepttools.modeling.algorithm.benders_decomposition.extract
• jijzepttools.modeling.algorithm.benders_decomposition.generate
• jijzepttools.modeling.algorithm.benders_decomposition.replace

Classes

BendersDecomposition	Benders Decomposition algorithm for mixed-integer programming.
BendersResult	Result of Benders decomposition iteration.

Package Contents

class BendersDecomposition(problem: jijmodeling.Problem, instance_data: dict, binary_vars: List[jijmodeling.BinaryVar] = None, slack_M: float = 1000.0, alpha_bounds: Tuple[float, float] = (-100000, 100000), use_pareto_optimal_cuts: bool = False, initial_core_point: Dict[str, Any] | None = None, use_two_phase: bool = False, phase1_tolerance: float = 1e-06, phase1_slack_M: float | None = None)

Benders Decomposition algorithm for mixed-integer programming.

This class implements the Benders decomposition algorithm that separates binary and continuous variables to solve large-scale mixed-integer problems more efficiently.

original_problem

instance_data

slack_M = 1000.0

phase1_slack_M = None

continuous_vars

coupling_constraints = []

alpha_var

lower_bound

upper_bound

cuts: List[jijmodeling.Constraint] = []

iteration_count = 0

sub_problem

use_pareto_optimal_cuts = False

core_point: Dict[str, Any] | None = None

use_two_phase = False

phase: int = 2

phase1_tolerance = 1e-06

phase1_converged: bool = False

phase1_lower_bound: float

phase1_upper_bound: float

master_problem

solve_master_problem(solver_callback: Callable[[ommx.v1.Instance], ommx.v1.Solution]) → Tuple[float, Dict[str, Any], float]

Solve the master problem using the provided callback.

Parameters:

solver_callback (tp.Callable[[Instance], Solution]) – Callback function to solve ommx Instance

Returns:

Master objective, binary solution, alpha value

Return type:

tp.Tuple[float, tp.Dict[str, tp.Any], float]

solve_original_problem(binary_solution: Dict[str, Any]) → ommx.v1.Solution

Solve the original problem with fixed binary variables. :param binary_solution: Fixed binary variable values :type binary_solution: tp.Dict[str, tp.Any]

Returns:

OMMX solution object

Return type:

Solution

solve_sub_problem(binary_solution: Dict[str, Any]) → Tuple[float, Dict[str, Any], Dict[str, numpy.ndarray], bool, ommx.v1.Solution]

Solve the subproblem with fixed binary variables.

Parameters:

binary_solution (tp.Dict[str, tp.Any]) – Fixed binary variable values

Returns:

Subproblem objective, continuous solution, dual variables, feasibility, solution

Return type:

tp.Tuple[float, tp.Dict, tp.Dict, bool, Solution]

solve_phase1_sub_problem(binary_solution: Dict[str, Any]) → Tuple[float, Dict[str, Any], Dict[str, numpy.ndarray], bool]

Solve Phase 1 subproblem with slack-only objective.

Phase 1 objective: minimize bigM * sum(slack_vars) This focuses purely on feasibility, not optimality.

Parameters:

binary_solution (tp.Dict[str, tp.Any]) – Fixed binary variable values

Returns:

Phase 1 objective (slack penalty), continuous solution, dual variables, feasibility

Return type:

tp.Tuple[float, tp.Dict, tp.Dict, bool]

solve_phase1_pareto_sub_problem(core_point: Dict[str, Any]) → Tuple[float, Dict[str, numpy.ndarray]]

Solve Phase 1 Pareto-optimal subproblem with core point.

Similar to solve_pareto_sub_problem but for Phase 1 (slack-only objective).

Parameters:

core_point (tp.Dict[str, tp.Any]) – Core point values for binary variables

Returns:

Phase 1 Pareto subproblem objective and dual variables

Return type:

tp.Tuple[float, tp.Dict[str, np.ndarray]]

solve_pareto_sub_problem(core_point: Dict[str, Any]) → Tuple[float, Dict[str, numpy.ndarray]]

Solve Pareto-optimal subproblem with core point.

This solves: max (b - y0)^T u s.t. A^T u <= c

The key difference from solve_sub_problem is that we fix binary variables to the CORE POINT values, not the current master solution. This generates Pareto-optimal dual variables for stronger cuts.

Uses self.pareto_sub_problem which has binary variables relaxed to continuous (0-1), allowing fractional core point values.

Parameters:

core_point (tp.Dict[str, tp.Any]) – Core point values for binary variables

Returns:

Pareto subproblem objective and dual variables

Return type:

tp.Tuple[float, tp.Dict[str, np.ndarray]]

add_cuts(dual_variables: Dict[str, numpy.ndarray], is_subproblem_feasible: bool) → int

Add Benders cuts to the master problem.

Parameters:

• dual_variables (tp.Dict[str, np.ndarray]) – Dual variables from subproblem

• is_subproblem_feasible (bool) – Whether subproblem was feasible

Returns:

Number of cuts added

Return type:

int

update_bounds(master_objective: float, subproblem_objective: float, alpha_value: float)

Update lower and upper bounds.

Parameters:

• master_objective (float) – Master problem objective value

• subproblem_objective (float) – Subproblem objective value

• binary_solution (tp.Dict[str, tp.Any]) – Current binary solution

is_converged(tolerance: float = 1e-06) → bool

Check if algorithm has converged.

Convergence is achieved when: 1. Gap (UB - LB) <= tolerance, OR 2. Gap < 0 (LB > UB due to integer rounding of alpha variable)

The second condition handles the case where alpha is an integer variable and gets rounded up, causing LB to slightly exceed UB. This is effectively convergence since we’ve found an optimal solution.

Parameters:

tolerance (float) – Convergence tolerance

Returns:

True if converged

Return type:

bool

iterate(solver_callback: Callable[[ommx.v1.Instance], ommx.v1.Solution]) → BendersResult

Perform one iteration of Benders decomposition.

In two-phase mode: - Phase 1: Solve Phase 1 subproblem (slack-only objective) - Phase 2: Solve regular subproblem (full objective)

Parameters:

solver_callback (tp.Callable[[Instance], Solution]) – Callback to solve master problem

Returns:

Result of current iteration

Return type:

BendersResult

solve(solver_callback: Callable[[ommx.v1.Instance], ommx.v1.Solution], max_iterations: int = 100, tolerance: float = 1e-06, verbose: bool = False) → BendersResult

Solve the problem using Benders decomposition.

In two-phase mode, this will run Phase 1 until convergence (LB=UB=0), then automatically transition to Phase 2.

Parameters:

• solver_callback (tp.Callable[[Instance], Solution]) – Callback to solve master problem

• max_iterations (int) – Maximum number of iterations (total for both phases)

• tolerance (float) – Convergence tolerance for Phase 2

• verbose (bool) – Whether to print iteration information

Returns:

Final result

Return type:

BendersResult

Example

>>> benders = BendersDecomposition(problem, instance_data, use_two_phase=True)
>>> result = benders.solve(OMMXHighsAdapter.solve, max_iterations=50, tolerance=1e-6, verbose=True)
>>> print(f"Converged: {result.converged}")
>>> print(f"Optimal value: {result.upper_bound}")

get_solution_summary(result: BendersResult) → str

Get a summary string of the solution.

Parameters:

result (BendersResult) – Solution result

Returns:

Summary string

Return type:

str

class BendersResult

Result of Benders decomposition iteration.

solution

OMMX solution object

Type:

Solution

master_objective

Master problem objective value

Type:

float

subproblem_objective

Subproblem objective value

Type:

float

lower_bound

Current lower bound

Type:

float

upper_bound

Current upper bound

Type:

float

is_feasible

Whether subproblem was feasible

Type:

bool

binary_solution

Solution values for binary variables

Type:

tp.Dict

continuous_solution

Solution values for continuous variables

Type:

tp.Dict

iteration

Iteration number

Type:

int

converged

Whether algorithm has converged

Type:

bool

pareto_subproblem_objective

Pareto subproblem objective value

Type:

float, optional

pareto_dual_variables

Dual variables from Pareto subproblem

Type:

tp.Dict, optional

core_point

Current core point for Pareto-optimal cuts

Type:

tp.Dict, optional

phase

Current phase (1 = feasibility, 2 = optimality)

Type:

int

phase1_converged

Whether Phase 1 has converged

Type:

bool

phase1_lower_bound

Phase 1 lower bound

Type:

float, optional

phase1_upper_bound

Phase 1 upper bound

Type:

float, optional

solution: ommx.v1.Solution | None

master_objective: float

subproblem_objective: float

lower_bound: float

upper_bound: float

is_feasible: bool

binary_solution: Dict[str, Any]

continuous_solution: Dict[str, Any]

iteration: int

converged: bool = False

pareto_subproblem_objective: float | None = None

pareto_dual_variables: Dict[str, numpy.ndarray] | None = None

core_point: Dict[str, Any] | None = None

phase: int = 2

phase1_converged: bool = False

phase1_lower_bound: float | None = None

phase1_upper_bound: float | None = None