jijpresolve

Submodules

Classes

Instance

The instance for JijPresolve, a wrapper of ommx::v1::Instance in OMMX Rust SDK rather than Python SDK.

Functions

milp_presolve(→ tuple[Any, dict])

Execute MILP presolve using PaPILO library and return the presolved instance with statistics.

presolve(→ Any)

Execute presolve in a preset order.

Package Contents

class jijpresolve.Instance

The instance for JijPresolve, a wrapper of ommx::v1::Instance in OMMX Rust SDK rather than Python SDK.

You need to convert OMMX Python SDK’s ommx.v1.Instance to this class jijpresolve.Instance for executing presolve.

Example

We here demonstrate the convert_single_linear_inequality_into_bounds() method to show how to use this class. It converts \(a x + b \leq 0\) formed constraints (we call it ‘single linear’) into the upper (\(x \leq -b/a\)) or lower (\(x \geq -b/a\)) bound of \(x\) according to the sign of \(a\).

First, import required modules.

>>> import jijpresolve
>>> from ommx.v1 import DecisionVariable, Instance, Function, Bound

Create an OMMX Python SDK’s instance.

>>> x = [DecisionVariable.continuous(i, lower=0.0, upper=3.0) for i in range(3)]
>>> ommx_instance = Instance.from_components(
...     decision_variables=x,
...     objective=sum(x),
...     constraints=[
...         (2 * x[0] <= 1).set_id(0),  # single linear inequality
...         (x[0] + x[1] + x[2] <= 1).set_id(1),
...     ],
...     sense=Instance.MAXIMIZE,
... )

Convert the OMMX Python SDK’s instance to jijpresolve’s instance.

>>> presolve_instance = jijpresolve.Instance(ommx_instance)

Execute presolve.

>>> presolve_instance.convert_single_linear_inequality_into_bounds()

Restore the OMMX Python SDK’s instance.

>>> instance: Instance = presolve_instance.to_ommx()
>>> instance.decision_variables_df.dropna(axis=1, how="all")
          kind  lower  upper subscripts
id
0   Continuous    0.0    0.5         []
1   Continuous    0.0    3.0         []
2   Continuous    0.0    3.0         []

>>> instance.constraints_df.dropna(axis=1, how="all")
   equality    type   used_ids subscripts
id
1       <=0  Linear  {0, 1, 2}         []

The single linear inequality \(2x_0 \leq 1\) is converted to the upper bound \(x_0 \in [0, 0.5]\).

>>> print(instance.removed_constraints_df[["removed_reason", "removed_reason.variable_id"]].to_string(max_colwidth=100))
                                 removed_reason  removed_reason.variable_id
id
0   convert_single_linear_inequality_into_bounds                          0

The converted constraint is stored in the removed_constraints field. removed_reason.variable_id contains the variable id whose bound is applied to.

to_ommx() → Any

Convert to OMMX Python SDK’s ommx.v1.Instance.

static from_bytes(bytes: Instance.from_bytes.bytes) → Instance

Decode from the protobuf-encoded OMMX Message. You should use __init__() in most cases.

to_bytes() → bytes

Encode to the protobuf-encoded OMMX Message. You should use to_ommx() in most cases.

convert_single_linear_equality_into_fixed_variables(atol: float = 1e-06) → None

Convert single linear equality \(a x + b = 0\) into fixed variable \(x = -b/a\).

Example

Ready to use the OMMX Python SDK’s instance.

>>> x = [DecisionVariable.continuous(i, lower=0.0, upper=3.0) for i in range(3)]
>>> ommx_instance = Instance.from_components(
...     decision_variables=x,
...     objective=sum(x),
...     constraints=[
...         (2 * x[0] == 1).set_id(0),  # single linear equality
...         (x[0] + x[1] + x[2] <= 1).set_id(1),
...     ],
...     sense=Instance.MAXIMIZE,
... )

Call this method

>>> presolve_instance = jijpresolve.Instance(ommx_instance)
>>> presolve_instance.convert_single_linear_equality_into_fixed_variables()
>>> instance: Instance = presolve_instance.to_ommx()

The fixed value is stored in the substituted_value field of the decision variable.

>>> instance.decision_variables_df.dropna(axis=1, how="all")
          kind  lower  upper subscripts substituted_value
id
0   Continuous    0.0    3.0         []               0.5
1   Continuous    0.0    3.0         []              <NA>
2   Continuous    0.0    3.0         []              <NA>

The fixed variable \(x_0 = 0.5\) is substituted to objective and constraints.

>>> instance.objective
Function(x1 + x2 + 0.5)

>>> instance.get_constraint_by_id(1)
Constraint(x1 + x2 - 0.5 <= 0)

The removed constraint is stored in the removed_constraints field.

>>> print(instance.removed_constraints_df[["removed_reason", "removed_reason.variable_id"]].to_string(max_colwidth=100))
                                        removed_reason removed_reason.variable_id
id
0  convert_single_linear_equality_into_fixed_variables                          0

The removed_reason.variable_id contains the variable id which has been fixed via this equality.

convert_single_linear_inequality_into_bounds(atol: float = 1e-06) → None

Converts single linear inequality \(a x + b \leq 0\) into the upper (\(x \leq -b/a\)) or lower (\(x \geq -b/a\)) bound of \(x\) according to the sign of \(a\).

See the example in this class Instance for more details.

find_fixed_variables_from_bounds(atol: float = 1e-06) → None

Find fixed variables from degenerated bounds \([a, a]\).

This also truncates the bounds of integer variables \([a, b]\) to \([\lceil a \rceil, \lfloor b \rfloor]\), and then check degeneration.

Example

Ready to use the OMMX Python SDK’s instance.

>>> x = [
...     DecisionVariable.continuous(0, lower=3.0, upper=3.0),  # fixed to 3
...     DecisionVariable.integer(1, lower=0.9, upper=1.1),  # Rounded to [1, 1], and fixed to 1
...     DecisionVariable.integer(2, lower=0.1, upper=3.1),  # Rounded to [1, 3]
... ]
>>> ommx_instance = Instance.from_components(
...     decision_variables=x,
...     objective=sum(x),
...     constraints=[
...         (x[0] + x[1] + x[2] <= 1).set_id(0),
...     ],
...     sense=Instance.MAXIMIZE,
... )

Call this method

>>> presolve_instance = jijpresolve.Instance(ommx_instance)
>>> presolve_instance.find_fixed_variables_from_bounds()
>>> instance: Instance = presolve_instance.to_ommx()

The bounds for the integer variable are rounded to integers, and degenerate bounds are fixed.

>>> instance.decision_variables_df.dropna(axis=1, how="all")
          kind  lower  upper subscripts substituted_value
id
0   Continuous    3.0    3.0         []               3.0
1      Integer    1.0    1.0         []               1.0
2      Integer    1.0    3.0         []              <NA>

The fixed variables are substituted to objective and constraints.

>>> instance.objective
Function(x2 + 4)
>>> instance.get_constraint_by_id(0)
Constraint(x2 + 3 <= 0)

This does not remove any constraints.

evaluate_constraint_bounds(atol: float = 1e-06) → None

Evaluate the bound of \(f(x)\) for the constraints \(f(x) \leq 0\) and \(f(x) = 0\) to remove trivial constraints and detect infeasibility.

Example

Ready to use the OMMX Python SDK’s instance.

>>> x = [DecisionVariable.continuous(i, lower=0.0, upper=2.0) for i in range(3)]
>>> ommx_instance = Instance.from_components(
...     decision_variables=x,
...     objective=sum(x),
...     constraints=[
...         (x[0] + x[1] >= 0).set_id(0),  # Trivial inequality
...         (x[0] + x[1] + x[2] <= 6).set_id(1),  # Trivial inequality
...         (x[0] + x[2] <= 0).set_id(2),  # Convert to equality
...     ],
...     sense=Instance.MAXIMIZE,
... )

Call this method

>>> presolve_instance = jijpresolve.Instance(ommx_instance)
>>> presolve_instance.evaluate_constraint_bounds(1e-7)
>>> instance: Instance = presolve_instance.to_ommx()

The trivial constraints are removed, and inequality \(f(x) \leq 0\) with evaluated bound \(f(x) \geq 0\) is converted to equality \(f(x) = 0\).

>>> instance.constraints_df.dropna(axis=1, how="all")
   equality    type used_ids subscripts
id
2        =0  Linear   {0, 2}         []

>>> instance.removed_constraints_df.dropna(axis=1, how="all")
   equality    type   used_ids subscripts              removed_reason
id
0       <=0  Linear     {0, 1}         []  evaluate_constraint_bounds
1       <=0  Linear  {0, 1, 2}         []  evaluate_constraint_bounds
Infeasible detection

Let’s create an infeasible inequality \(x_0 + x_1 \leq -1\) for \(x_0, x_1 \in [0, 2]\).

>>> x = [DecisionVariable.continuous(i, lower=0.0, upper=2.0) for i in range(3)]
>>> ommx_instance = Instance.from_components(
...     decision_variables=x,
...     objective=sum(x),
...     constraints=[(x[0] + x[1] <= -1).set_id(0)], # x[0] + x[1] must be positive
...     sense=Instance.MAXIMIZE,
... )

When infeasible, this method raises a RuntimeError.

>>> presolve_instance = jijpresolve.Instance(ommx_instance)
>>> presolve_instance.evaluate_constraint_bounds(1e-7)
Traceback (most recent call last):
...
RuntimeError: The bound of `f(x)` in the inequality `f(x) <= 0` (ID=0) is inconsistent: Bound[1, 5]

Similarly, for equality \(f(x) = 0\) the bound of \(f(x)\) does not contains \(0\), this raises a RuntimeError.

milp_presolve(dual_reductions: str = 'strong', threads: int = 1, randomseed: int = 0) → dict

Perform MILP presolve using PaPILO library and modify the instance in place.

This method applies a comprehensive set of presolve techniques to the MILP problem, including domain propagation, constraint aggregation, and variable elimination.

For detailed parameter descriptions, examples, and usage patterns, see milp_presolve().

jijpresolve.milp_presolve(instance: Any, dual_reductions: str = 'strong', threads: int = 1, randomseed: int = 0) → tuple[Any, dict]

Execute MILP presolve using PaPILO library and return the presolved instance with statistics.

This function applies a comprehensive set of presolve techniques to the MILP problem, including domain propagation, constraint aggregation, and variable elimination. Unlike Instance.milp_presolve() which modifies the instance in place, this function returns a new presolved instance along with statistics.

Parameters:

  • instance (ommx.v1.Instance): The OMMX instance to presolve

  • dual_reductions (str, optional): Level of dual reductions to apply. Must be one of following:

    • disable: Disable all dual reductions

    • weak: Preserving the set of optimal solutions

    • strong: Preserving the optimal objective value (default)

  • threads (int, optional): Number of threads to use for presolving (default: 1)

    • 0: Automatic detection

    • 1: Single-threaded (default)

    • N > 1: Use N threads for parallel presolving

  • randomseed (int, optional): Random seed value for reproducibility (default: 0)

Returns:

tuple[ommx.v1.Instance, dict]: A tuple containing:

  • Presolved OMMX instance

  • Statistics dictionary with keys such as: presolve_time, rounds, deleted_columns, deleted_rows, and more

Example

Basic usage with a simple instance

>>> from ommx.v1 import DecisionVariable, Instance
>>> import jijpresolve
>>> x = [DecisionVariable.integer(i, lower=0, upper=10) for i in range(3)]
>>> ommx_instance = Instance.from_components(
...     decision_variables=x,
...     objective=sum(x),
...     constraints=[
...         (x[0] + x[1] + x[2] <= 5).set_id(0),
...     ],
...     sense=Instance.MAXIMIZE,
... )
>>> presolved_instance, stats = jijpresolve.milp_presolve(ommx_instance)
>>> stats['rounds']
2
>>> stats['deleted_columns']
3

The original instance is not modified:

>>> ommx_instance.stats()['decision_variables']['by_usage']['fixed']
0
>>> presolved_instance.stats()['decision_variables']['by_usage']['fixed']
3

Using MIPLIB instance

>>> import jijpresolve
>>> from ommx import dataset
>>> ommx_instance = dataset.miplib2017("g503inf")
>>> presolved_instance, stats = jijpresolve.milp_presolve(ommx_instance)
>>> stats['rounds']
7
>>> stats['deleted_columns']
10
>>> stats['deleted_rows']
6

Compare before and after:

>>> ommx_instance.stats()['decision_variables']['total']
48
>>> ommx_instance.stats()['constraints']['active']
41

>>> presolved_instance.stats()['constraints']['active']
35
>>> presolved_instance.stats()['constraints']['removed']
6
>>> presolved_instance.stats()['decision_variables']['total']
48
>>> presolved_instance.stats()['decision_variables']['by_usage']['fixed']
8

This demonstrates the effectiveness of MILP presolve on larger problem instances.

jijpresolve.presolve(instance: Any, atol: float = 1e-07) → Any

Execute presolve in a preset order.

Currently this function executes the following presolve steps:

Important

The algorithm of this function is not guaranteed to be stable. This function is designed as a better choice for users who do not want to handle the details of presolve and are open to algorithm improvements.

Example

Ready the OMMX Python SDK’s instance.

>>> from ommx.v1 import DecisionVariable, Instance
>>> x = [DecisionVariable.continuous(i, lower=0.0, upper=3.0) for i in range(3)]
>>> ommx_instance = Instance.from_components(
...     decision_variables=x,
...     objective=sum(x),
...     constraints=[
...         (2 * x[0] <= 1).set_id(0),
...         (x[0] + x[1] + x[2] <= 1).set_id(1),
...     ],
...     sense=Instance.MAXIMIZE,
... )

Call this method

>>> import jijpresolve
>>> presolved_instance = jijpresolve.presolve(ommx_instance)

The input instance is not modified, and a new presolved instance is returned.

>>> presolved_instance.decision_variables_df.dropna(axis=1, how="all")
          kind  lower  upper subscripts
id
0   Continuous    0.0    0.5         []
1   Continuous    0.0    3.0         []
2   Continuous    0.0    3.0         []

>>> presolved_instance.constraints_df.dropna(axis=1, how="all")
   equality    type   used_ids subscripts
id
1       <=0  Linear  {0, 1, 2}         []

The single linear inequality \(2x_0 \leq 1\) is converted to the upper bound \(x_0 \in [0, 0.5]\) by convert_single_linear_inequality_into_bounds().