jijpresolve.jijpresolve

Classes

Instance

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

Functions

milp_presolve(→ tuple[ommx.Instance, dict])

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

presolve(→ ommx.Instance)

Execute presolve in a preset order.

Module Contents

class jijpresolve.jijpresolve.Instance

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

You need to convert OMMX Python SDK’s ommx.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 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={
...         0: 2 * x[0] <= 1,  # single linear inequality
...         1: x[0] + x[1] + x[2] <= 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()
>>> float(instance.decision_variables_df().loc[0, "upper"])
0.5

>>> list(instance.constraints)
[1]

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

>>> instance.removed_constraints[0].removed_reason
'convert_single_linear_inequality_into_bounds'
>>> instance.removed_constraints[0].removed_reason_parameters
{'variable_id': '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() → ommx.Instance

Convert to OMMX Python SDK’s ommx.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={
...         0: 2 * x[0] == 1,  # single linear equality
...         1: x[0] + x[1] + x[2] <= 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 on the owning instance.

>>> instance.fixed_decision_variables()[0]
0.5

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

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

>>> instance.constraints[1]
Constraint(x1 + x2 - 0.5 <= 0)

The removed constraint is stored in the removed_constraints field.

>>> instance.removed_constraints[0].removed_reason
'convert_single_linear_equality_into_fixed_variables'
>>> instance.removed_constraints[0].removed_reason_parameters
{'variable_id': '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={0: x[0] + x[1] + x[2] <= 1},
...     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.fixed_decision_variables()
{0: 3.0, 1: 1.0}
>>> float(instance.decision_variables_df().loc[2, "lower"])
1.0

The fixed variables are substituted to objective and constraints.

>>> instance.objective
Function(x2 + 4)
>>> instance.constraints[0].function.almost_equal(Function(x[2] + 3.0))
True

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={
...         0: x[0] + x[1] >= 0,  # Trivial inequality
...         1: x[0] + x[1] + x[2] <= 6,  # Trivial inequality
...         2: x[0] + x[2] <= 0,  # 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\).

>>> str(instance.constraints[2].equality) == "=0"
True

>>> sorted(instance.removed_constraints)
[0, 1]
>>> instance.removed_constraints[0].removed_reason
'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={0: x[0] + x[1] <= -1}, # 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.jijpresolve.milp_presolve(instance: Any, dual_reductions: str = 'strong', threads: int = 1, randomseed: int = 0) → tuple[ommx.Instance, 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.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.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 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={0: x[0] + x[1] + x[2] <= 5},
...     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)
assert stats["rounds"] == 7
assert stats["deleted_columns"] == 10
assert stats["deleted_rows"] == 6

assert ommx_instance.stats()["decision_variables"]["total"] == 48
assert ommx_instance.stats()["constraints"]["active"] == 41
assert presolved_instance.stats()["constraints"]["active"] == 35
assert presolved_instance.stats()["constraints"]["removed"] == 6
assert presolved_instance.stats()["decision_variables"]["total"] == 48
assert presolved_instance.stats()["decision_variables"]["by_usage"]["fixed"] == 8

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

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

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 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={
...         0: 2 * x[0] <= 1,
...         1: x[0] + x[1] + x[2] <= 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.

>>> float(presolved_instance.decision_variables_df().loc[0, "upper"])
0.5

>>> list(presolved_instance.constraints)
[1]

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().