jijzepttools.modeling.algorithm.benders_decomposition

Contents

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#

Classes#

BendersDecomposition

Benders Decomposition algorithm for mixed-integer programming.

BendersResult

Result of Benders decomposition iteration.

CutInfo

Metadata for a Benders cut.

CutType

Type of Benders cut.

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, max_cuts: int | None = 100, max_samples: int | None = None, round_cut_coefficients: bool = False)#

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#
round_cut_coefficients = False#
continuous_vars#
coupling_constraints = []#
alpha_var#
lower_bound#
upper_bound#
cut_infos: List[CutInfo] = []#
iteration_count = 0#
max_cuts = 100#
max_samples = None#
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#
property cuts: List[jijmodeling.Constraint]#

Get list of cut constraints (for backward compatibility).

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

Solve the master problem using the provided callback.

Supports callbacks that return either Solution or SampleSet. When SampleSet is returned, multiple binary solutions are extracted (limited by max_samples, sorted by objective value).

For SampleSet results (heuristic solvers), each solution is checked for feasibility against master problem constraints. Infeasible solutions are still returned but marked as such, since they can still generate valid Benders cuts.

Parameters:

solver_callback – Callback function that takes ommx Instance and returns Solution or SampleSet.

Returns:

Tuple of (best_objective, binary_solutions_list, alpha_values_list,

feasibility_list, raw_result).

  • best_objective: Best objective value from feasible solutions (or all if none feasible)

  • binary_solutions_list: List of binary variable dictionaries

  • alpha_values_list: List of alpha values corresponding to each solution

  • feasibility_list: List of booleans indicating master feasibility for each solution

  • raw_result: Original Solution or SampleSet from callback

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, binary_key: tuple | None = None) → 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

  • binary_key (tuple, optional) – Hashable key identifying the binary solution

Returns:

Number of cuts added

Return type:

int

update_bounds(master_objective: float, subproblem_objective: float, alpha_value: float, binary_solution: Dict[str, Any])#

Update lower and upper bounds.

Parameters:

  • master_objective (float) – Master problem objective value (from feasible solution only)

  • subproblem_objective (float) – Subproblem objective value

  • alpha_value (float) – Alpha variable value from master solution

  • 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 | ommx.v1.SampleSet]) → BendersResult#

Perform one iteration of Benders decomposition.

Supports multi-cut generation when solver returns SampleSet. Each sample generates its own cut, potentially accelerating convergence.

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

Parameters:

solver_callback – Callback to solve master problem. Can return Solution or SampleSet.

Returns:

Result of current iteration

Return type:

BendersResult

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

Solve the problem using Benders decomposition.

Supports multi-cut generation when solver_callback returns SampleSet. In two-phase mode, this will run Phase 1 until convergence (LB=UB=0), then automatically transition to Phase 2.

Parameters:

  • solver_callback – Callback to solve master problem. Can return Solution or SampleSet. When SampleSet is returned, multiple cuts are generated per iteration.

  • 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

num_cuts_added#

Number of cuts added in this iteration

Type:

int

num_samples_processed#

Number of samples processed in this iteration

Type:

int

num_master_feasible#

Number of master-feasible samples (for SampleSet callbacks)

Type:

int

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#
num_cuts_added: int = 0#
num_samples_processed: int = 1#
num_master_feasible: int = 1#
class CutInfo#

Metadata for a Benders cut.

constraint#

The jijmodeling constraint representing the cut

Type:

jm.Constraint

cut_type#

Type of cut (feasibility or optimality)

Type:

CutType

iteration#

Iteration when the cut was generated

Type:

int

slack#

Current slack value in master problem (0 = tight/active)

Type:

float

binary_key#

Hashable key identifying the binary solution that generated this cut

Type:

tuple

constraint: jijmodeling.Constraint#
cut_type: CutType#
iteration: int#
slack: float = 0.0#
binary_key: tuple | None = None#
class CutType#

Bases: enum.Enum

Type of Benders cut.

FEASIBILITY = 'feasibility'#
OPTIMALITY = 'optimality'#
Contents