jijzepttools.modeling.algorithm.benders_decomposition.replace

jijzepttools.modeling.algorithm.benders_decomposition.replace#

Expression replacement functions for Benders decomposition.

This module provides functions to replace expressions with fixed values, placeholders, and create slack variables for the Benders decomposition algorithm.

Functions#

replace_binary_with_placeholders(→ Tuple[Any, ...)

Replace binary variables with placeholders.

extract_constraint_terms_by_variable_type(→ Tuple[Any, ...)

Extract constraint terms by variable type (binary vs continuous).

create_dual_expression(→ Any)

Create dual expression for Benders cuts.

Module Contents#

replace_binary_with_placeholders(expression: Any, binary_vars: List[jijmodeling.BinaryVar], placeholder_prefix: str = 'fixed_') → Tuple[Any, Dict[str, jijmodeling.Placeholder]]#

Replace binary variables with placeholders.

Parameters:

  • expression (jm.Expression) – Expression to modify

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

  • placeholder_prefix (str) – Prefix for placeholder names

Returns:

(modified_expression, placeholder_dict)

Return type:

tp.Tuple[jm.Expression, tp.Dict[str, jm.Placeholder]]

extract_constraint_terms_by_variable_type(constraint: jijmodeling.Constraint, binary_vars: List[jijmodeling.BinaryVar]) → Tuple[Any, Any]#

Extract constraint terms by variable type (binary vs continuous).

Parameters:

  • constraint (jm.Constraint) – Constraint to analyze

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

Returns:

(binary_terms, continuous_terms)

Return type:

tp.Tuple[tp.Any, tp.Any]

create_dual_expression(constraint: jijmodeling.Constraint, dual_variable: jijmodeling.Placeholder, constraint_rhs: Any) → Any#

Create dual expression for Benders cuts.

For a constraint Ax <= b with dual variable λ, creates λ * b

Parameters:

  • constraint (jm.Constraint) – Original constraint

  • dual_variable (jm.Placeholder) – Dual variable placeholder

  • constraint_rhs (jm.Expression) – Right-hand side expression

Returns:

Dual expression λ * b

Return type:

jm.Expression

Example

>>> constraint = jm.Constraint("c1", A*x <= b, forall=[i])
>>> dual_var = jm.Placeholder("lambda_c1", shape=(5,))
>>> dual_expr = create_dual_expression(constraint, dual_var, b)
>>> # Creates sum over i of lambda_c1[i] * b[i]
Contents