jijpresolve
===========

.. py:module:: jijpresolve


Submodules
----------

.. toctree::
   :maxdepth: 1

   /autoapi/jijpresolve/jijpresolve/index


Classes
-------

.. autoapisummary::

   jijpresolve.Instance


Functions
---------

.. autoapisummary::

   jijpresolve.milp_presolve
   jijpresolve.presolve


Package Contents
----------------

.. py:class:: 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 :meth:`convert_single_linear_inequality_into_bounds` method to show how to use this class.
   It converts :math:`a x + b \leq 0` formed constraints (we call it 'single linear')
   into the upper (:math:`x \leq -b/a`) or lower (:math:`x \geq -b/a`) bound of :math:`x` according to the sign of :math:`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 :math:`2x_0 \leq 1` is converted to the upper bound :math:`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.


   .. py:method:: to_ommx() -> Any

      Convert to OMMX Python SDK's ``ommx.v1.Instance``.



   .. py:method:: from_bytes(bytes: Instance.from_bytes.bytes) -> Instance
      :staticmethod:


      Decode from the protobuf-encoded OMMX Message. You should use :meth:`__init__` in most cases.



   .. py:method:: to_bytes() -> bytes

      Encode to the protobuf-encoded OMMX Message. You should use :meth:`to_ommx` in most cases.



   .. py:method:: convert_single_linear_equality_into_fixed_variables(atol: float = 1e-06) -> None

      Convert single linear equality :math:`a x + b = 0` into fixed variable :math:`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 :math:`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.



   .. py:method:: convert_single_linear_inequality_into_bounds(atol: float = 1e-06) -> None

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

      See the example in this class :class:`Instance` for more details.



   .. py:method:: find_fixed_variables_from_bounds(atol: float = 1e-06) -> None

      Find fixed variables from degenerated bounds :math:`[a, a]`.

      This also truncates the bounds of integer variables :math:`[a, b]` to :math:`[\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.



   .. py:method:: evaluate_constraint_bounds(atol: float = 1e-06) -> None

      Evaluate the bound of :math:`f(x)` for the constraints :math:`f(x) \leq 0` and :math:`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 :math:`f(x) \leq 0` with evaluated bound :math:`f(x) \geq 0` is converted to equality :math:`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 :math:`x_0 + x_1 \leq -1` for :math:`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 :math:`f(x) = 0` the bound of :math:`f(x)` does not contains :math:`0`, this raises a ``RuntimeError``.



   .. py:method:: 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 :func:`milp_presolve`.



.. py:function:: 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 :meth:`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.


.. py:function:: presolve(instance: Any, atol: float = 1e-07) -> Any

   Execute presolve in a preset order.

   Currently this function executes the following presolve steps:

   * :meth:`Instance.find_fixed_variables_from_bounds`
   * :meth:`Instance.convert_single_linear_equality_into_fixed_variables`
   * :meth:`Instance.convert_single_linear_inequality_into_bounds`
   * :meth:`Instance.evaluate_constraint_bounds`

   .. 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 :math:`2x_0 \leq 1` is converted to the upper bound :math:`x_0 \in [0, 0.5]`
   by :meth:`convert_single_linear_inequality_into_bounds`.