jijzepttools.modeling.algorithm.benders_decomposition.extract

jijzepttools.modeling.algorithm.benders_decomposition.extract#

Variable and constraint extraction functions for Benders decomposition.

This module provides functions to extract different types of variables and constraints from a JiJModeling problem to support Benders decomposition.

Functions#

`extract_binary_variables`(→ List[jijmodeling.BinaryVar])	Extract all binary variables from the problem.
`extract_continuous_variables`(...)	Extract all continuous variables from the problem.
`extract_integer_variables`(→ List[jijmodeling.IntegerVar])	Extract all integer variables from the problem.
`extract_master_constraints`(→ List[jijmodeling.Constraint])	Extract constraints that contain only binary variables (master problem constraints).
`extract_subproblem_constraints`(...)	Extract constraints that contain continuous variables (subproblem constraints).
`extract_coupling_constraints`(...)	Extract constraints that contain both binary and continuous variables (coupling constraints).
`separate_objective_by_variable_type`(→ Tuple[Any, Any])	Separate objective function into binary and continuous parts.

Module Contents#

extract_binary_variables(problem: jijmodeling.Problem) → List[jijmodeling.BinaryVar]#

Extract all binary variables from the problem.

Parameters:: problem (jm.Problem) – The optimization problem
Returns:: List of binary variables
Return type:: tp.List[jm.BinaryVar]

Example

>>> x = jm.BinaryVar("x", shape=(2,))
>>> y = jm.ContinuousVar("y", shape=(2,), lower_bound=0)
>>> problem = jm.Problem("test")
>>> problem += x[0] + y[0]
>>> binary_vars = extract_binary_variables(problem)
>>> len(binary_vars)
1
>>> binary_vars[0].name
'x'

extract_continuous_variables(problem: jijmodeling.Problem) → List[jijmodeling.ContinuousVar]#

Extract all continuous variables from the problem.

Parameters:: problem (jm.Problem) – The optimization problem
Returns:: List of continuous variables
Return type:: tp.List[jm.ContinuousVar]

Example

>>> x = jm.BinaryVar("x", shape=(2,))
>>> y = jm.ContinuousVar("y", shape=(2,), lower_bound=0)
>>> problem = jm.Problem("test")
>>> problem += x[0] + y[0]
>>> continuous_vars = extract_continuous_variables(problem)
>>> len(continuous_vars)
1
>>> continuous_vars[0].name
'y'

extract_integer_variables(problem: jijmodeling.Problem) → List[jijmodeling.IntegerVar]#

Extract all integer variables from the problem.

Parameters:: problem (jm.Problem) – The optimization problem
Returns:: List of integer variables
Return type:: tp.List[jm.IntegerVar]

extract_master_constraints(problem: jijmodeling.Problem, binary_vars: List[jijmodeling.BinaryVar]) → List[jijmodeling.Constraint]#

Extract constraints that contain only binary variables (master problem constraints).

Parameters:

problem (jm.Problem) – The optimization problem
binary_vars (tp.List[jm.BinaryVar]) – List of binary variables

Returns:

Constraints containing only binary variables

Return type:

tp.List[jm.Constraint]

Example

>>> x = jm.BinaryVar("x", shape=(2,))
>>> y = jm.ContinuousVar("y", shape=(2,), lower_bound=0)
>>> problem = jm.Problem("test")
>>> problem += jm.Constraint("c1", x[0] + x[1] <= 1)  # Binary only
>>> problem += jm.Constraint("c2", x[0] + y[0] <= 2)  # Mixed
>>> master_constraints = extract_master_constraints(problem, [x])
>>> len(master_constraints)
1
>>> master_constraints[0].name
'c1'

extract_subproblem_constraints(problem: jijmodeling.Problem, binary_vars: List[jijmodeling.BinaryVar]) → List[jijmodeling.Constraint]#

Extract constraints that contain continuous variables (subproblem constraints).

Parameters:

problem (jm.Problem) – The optimization problem
binary_vars (tp.List[jm.BinaryVar]) – List of binary variables

Returns:

Constraints containing continuous variables

Return type:

tp.List[jm.Constraint]

Example

>>> x = jm.BinaryVar("x", shape=(2,))
>>> y = jm.ContinuousVar("y", shape=(2,), lower_bound=0)
>>> problem = jm.Problem("test")
>>> problem += jm.Constraint("c1", x[0] + x[1] <= 1)  # Binary only
>>> problem += jm.Constraint("c2", x[0] + y[0] <= 2)  # Mixed
>>> problem += jm.Constraint("c3", y[0] + y[1] <= 3)  # Continuous only
>>> sub_constraints = extract_subproblem_constraints(problem, [x])
>>> len(sub_constraints)
2
>>> sorted([c.name for c in sub_constraints])
['c2', 'c3']

extract_coupling_constraints(problem: jijmodeling.Problem, binary_vars: List[jijmodeling.BinaryVar]) → List[jijmodeling.Constraint]#

Extract constraints that contain both binary and continuous variables (coupling constraints).

Parameters:

problem (jm.Problem) – The optimization problem
binary_vars (tp.List[jm.BinaryVar]) – List of binary variables

Returns:

Constraints containing both binary and continuous variables

Return type:

tp.List[jm.Constraint]

Example

>>> x = jm.BinaryVar("x", shape=(2,))
>>> y = jm.ContinuousVar("y", shape=(2,), lower_bound=0)
>>> problem = jm.Problem("test")
>>> problem += jm.Constraint("c1", x[0] + x[1] <= 1)  # Binary only
>>> problem += jm.Constraint("c2", x[0] + y[0] <= 2)  # Mixed (coupling)
>>> problem += jm.Constraint("c3", y[0] + y[1] <= 3)  # Continuous only
>>> coupling_constraints = extract_coupling_constraints(problem, [x])
>>> len(coupling_constraints)
1
>>> coupling_constraints[0].name
'c2'

separate_objective_by_variable_type(objective: Any, binary_vars: List[jijmodeling.BinaryVar]) → Tuple[Any, Any]#

Separate objective function into binary and continuous parts.

Parameters:

objective (jm.Expression) – The objective function
binary_vars (tp.List[jm.BinaryVar]) – List of binary variables

Returns:

(binary_part, continuous_part)

Return type:

tp.Tuple[jm.Expression, jm.Expression]

Example

>>> x = jm.BinaryVar("x", shape=(2,))
>>> y = jm.ContinuousVar("y", shape=(2,), lower_bound=0)
>>> objective = 3*x[0] + 2*x[1] + 4*y[0] + 5*y[1]
>>> binary_part, continuous_part = separate_objective_by_variable_type(objective, [x])
>>> # binary_part should contain 3*x[0] + 2*x[1]
>>> # continuous_part should contain 4*y[0] + 5*y[1]