jijzepttools.modeling.algorithm.benders_decomposition.generate

jijzepttools.modeling.algorithm.benders_decomposition.generate#

Problem generation functions for Benders decomposition.

This module provides functions to generate master problems, subproblems, and Benders cuts for the decomposition algorithm.

Functions#

generate_master_problem(→ jijmodeling.Problem)

Generate master problem containing only binary variables and α variable.

generate_subproblem(→ jijmodeling.Problem)

Generate subproblem with continuous variables and slack variables using generate_always_feasible_problem_forall.

generate_phase1_subproblem(→ jijmodeling.Problem)

Generate Phase 1 subproblem with slack-only objective for two-phase Benders.

generate_phase1_pareto_subproblem(→ jijmodeling.Problem)

Generate Phase 1 Pareto-optimal subproblem with relaxed binary variables.

generate_pareto_subproblem(→ jijmodeling.Problem)

Generate Pareto-optimal subproblem with binary variables relaxed to continuous.

generate_cut_term(→ Any)

Generate Benders feasibility cut.

create_alpha_variable(→ jijmodeling.IntegerVar)

Create α variable for master problem objective bound.

create_slack_penalty_placeholder(→ jijmodeling.Placeholder)

Create placeholder for slack variable penalty coefficient.

Module Contents#

generate_master_problem(original_problem: jijmodeling.Problem, binary_vars: List[jijmodeling.BinaryVar], alpha_var: jijmodeling.IntegerVar | None = None, cuts: List[jijmodeling.Constraint] = None, phase1_mode: bool = False) → jijmodeling.Problem#

Generate master problem containing only binary variables and α variable.

The master problem includes: - Binary variables from original problem - α variable (represents lower bound on continuous part) - Constraints involving only binary variables - Benders cuts (feasibility and optimality cuts)

Parameters:

  • original_problem (jm.Problem) – Original mixed-integer problem

  • binary_vars (tp.List[jm.BinaryVar]) – Binary variables for master problem

  • alpha_var (jm.DecisionVariable, optional) – α variable for objective bound

  • cuts (tp.List[jm.Constraint], optional) – Benders cuts to add

  • phase1_mode (bool) – If True, generate Phase 1 master problem with objective = α only (no binary cost term). Used for two-phase Benders where Phase 1 minimizes slack penalty only.

Returns:

Master problem

Return type:

jm.Problem

Example

>>> x = jm.BinaryVar("x", shape=(2,))
>>> y = jm.ContinuousVar("y", shape=(2,), lower_bound=0)
>>> problem = jm.Problem("orig")
>>> problem += 3*x[0] + 2*x[1] + 4*y[0] + 5*y[1]  # objective
>>> problem += jm.Constraint("c1", x[0] + x[1] <= 1)  # master constraint
>>> master = generate_master_problem(problem, [x])
>>> # master problem contains: min α + 3*x[0] + 2*x[1] s.t. x[0] + x[1] <= 1
>>> master_phase1 = generate_master_problem(problem, [x], phase1_mode=True)
>>> # Phase 1 master contains: min α s.t. x[0] + x[1] <= 1
generate_subproblem(original_problem: jijmodeling.Problem, binary_vars: List[jijmodeling.BinaryVar], use_always_feasible: bool = True, slack_M: float = 1000.0, exclude_constraints: List[str] | None = None) → jijmodeling.Problem#

Generate subproblem with continuous variables and slack variables using generate_always_feasible_problem_forall.

The subproblem includes: - Continuous variables from original problem - Slack variables to ensure feasibility (added by generate_always_feasible_problem_forall) - Binary variables replaced with placeholders (to be fixed)

Parameters:

  • original_problem (jm.Problem) – Original mixed-integer problem

  • binary_vars (tp.List[jm.BinaryVar]) – Binary variables (to be replaced)

  • use_always_feasible (bool) – Whether to use always feasible transformation

  • slack_M (float) – Penalty coefficient for slack variables

  • exclude_constraints (tp.Optional[tp.List[str]], optional) – List of constraint names to exclude from slack variables. Defaults to None.

Returns:

Subproblem with continuous variables and slack variables

Return type:

jm.Problem

Example

>>> x = jm.BinaryVar("x", shape=(2,))
>>> y = jm.ContinuousVar("y", shape=(2,), lower_bound=0, upper_bound=10)
>>> problem = jm.Problem("orig")
>>> problem += 3*x[0] + 2*x[1] + 4*y[0] + 5*y[1]  # objective
>>> problem += jm.Constraint("c2", x[0] + y[0] <= 2)  # subproblem constraint
>>> subproblem = generate_subproblem(problem, [x])
generate_phase1_subproblem(original_problem: jijmodeling.Problem, binary_vars: List[jijmodeling.BinaryVar], exclude_constraints: List[str] | None = None, slack_bound: int = 100000000) → jijmodeling.Problem#

Generate Phase 1 subproblem with slack-only objective for two-phase Benders.

Phase 1 focuses on feasibility only. The objective is:

minimize bigM * sum(slack_vars)

The original continuous objective (c^T y) is NOT included. This allows generating cuts that are independent of the objective function, making them reusable across different objective functions with the same feasible region.

Note: The bigM penalty coefficient is provided via instance_data[“bigM”] at solve time, not as a parameter to this function.

Parameters:

  • original_problem (jm.Problem) – Original mixed-integer problem

  • binary_vars (tp.List[jm.BinaryVar]) – Binary variables (to be replaced)

  • exclude_constraints (tp.Optional[tp.List[str]], optional) – List of constraint names to exclude from slack variables. Defaults to None.

  • slack_bound (int) – Upper bound for slack variables. Defaults to 100000000. This should be large enough to ensure feasibility.

Returns:

Phase 1 subproblem with slack-only objective

Return type:

jm.Problem

Example

>>> x = jm.BinaryVar("x", shape=(2,))
>>> y = jm.ContinuousVar("y", shape=(2,), lower_bound=0, upper_bound=10)
>>> problem = jm.Problem("orig")
>>> problem += 3*x[0] + 2*x[1] + 4*y[0] + 5*y[1]  # objective
>>> problem += jm.Constraint("c2", x[0] + y[0] <= 2)  # subproblem constraint
>>> phase1_subproblem = generate_phase1_subproblem(problem, [x])
>>> # Phase 1 objective: minimize bigM * (v + w), NOT including 4*y[0] + 5*y[1]
generate_phase1_pareto_subproblem(original_problem: jijmodeling.Problem, binary_vars: List[jijmodeling.BinaryVar], exclude_constraints: List[str] | None = None, slack_bound: int = 100000000) → jijmodeling.Problem#

Generate Phase 1 Pareto-optimal subproblem with relaxed binary variables.

This is the Phase 1 version of generate_pareto_subproblem(). Binary variables are relaxed to continuous (0 <= x <= 1) to allow fractional core point values for Magnanti-Wong method.

The objective is slack-only: minimize bigM * sum(slack_vars)

Note: The bigM penalty coefficient is provided via instance_data[“bigM”] at solve time.

Parameters:

  • original_problem (jm.Problem) – Original mixed-integer problem

  • binary_vars (tp.List[jm.BinaryVar]) – Binary variables (to be relaxed to continuous)

  • exclude_constraints (tp.Optional[tp.List[str]], optional) – Constraint names to exclude.

  • slack_bound (int) – Upper bound for slack variables. Defaults to 100000000.

Returns:

Phase 1 Pareto subproblem with relaxed binary variables

Return type:

jm.Problem

generate_pareto_subproblem(original_problem: jijmodeling.Problem, binary_vars: List[jijmodeling.BinaryVar], use_always_feasible: bool = True, slack_M: float = 1000.0, exclude_constraints: List[str] | None = None) → jijmodeling.Problem#

Generate Pareto-optimal subproblem with binary variables relaxed to continuous.

This subproblem is used for generating Pareto-optimal cuts (Magnanti-Wong method). The key difference from generate_subproblem is that binary variables are replaced with continuous variables (0 <= x <= 1) to allow fractional core point values.

Parameters:

  • original_problem (jm.Problem) – Original mixed-integer problem

  • binary_vars (tp.List[jm.BinaryVar]) – Binary variables (to be relaxed to continuous)

  • use_always_feasible (bool) – Whether to use always feasible transformation

  • slack_M (float) – Penalty coefficient for slack variables

  • exclude_constraints (tp.Optional[tp.List[str]], optional) – Constraint names to exclude from slack.

Returns:

Pareto subproblem with relaxed binary variables (as continuous 0-1)

Return type:

jm.Problem

generate_cut_term(constraint: jijmodeling.Constraint, dual_variable: jijmodeling.Placeholder, binary_vars: List[jijmodeling.BinaryVar]) → Any#

Generate Benders feasibility cut.

Feasibility cut: Σ λᵢ * gᵢ(x) ≤ 0 where gᵢ(x) is the binary part of constraint i

Parameters:

  • constraint (jm.Constraint) – Original coupling constraint

  • dual_variable (jm.Placeholder) – Dual variable from subproblem

  • binary_vars (tp.List[jm.BinaryVar]) – Binary variables

Returns:

expression for feasibility cut

Return type:

tp.Any

Example

>>> # For constraint: 2*x[0] + 3*y[0] <= 5
>>> # With dual variable λ = 2.0
>>> # Creates feasibility cut: 2.0 * 2*x[0] <= 0  (simplified: 4*x[0] <= 0)
create_alpha_variable(name: str = 'alpha', lower_bound: float = -100000, upper_bound: float = 100000) → jijmodeling.IntegerVar#

Create α variable for master problem objective bound.

Parameters:

  • name (str) – Variable name

  • lower_bound (float) – Lower bound

  • upper_bound (float) – Upper bound

Returns:

Alpha variable

Return type:

jm.IntegerVar

Example

>>> alpha = create_alpha_variable()
>>> # Creates integer variable α ∈ [-100000, 100000]
create_slack_penalty_placeholder(name: str = 'slack_M') → jijmodeling.Placeholder#

Create placeholder for slack variable penalty coefficient.

Parameters:

name (str) – Placeholder name

Returns:

Slack penalty placeholder

Return type:

jm.Placeholder

Example

>>> slack_M = create_slack_penalty_placeholder()
>>> # Creates placeholder for slack penalty coefficient
Contents