ortools.math_opt.python.statistics

  1#!/usr/bin/env python3
  2# Copyright 2010-2025 Google LLC
  3# Licensed under the Apache License, Version 2.0 (the "License");
  4# you may not use this file except in compliance with the License.
  5# You may obtain a copy of the License at
  6#
  7#     http://www.apache.org/licenses/LICENSE-2.0
  8#
  9# Unless required by applicable law or agreed to in writing, software
 10# distributed under the License is distributed on an "AS IS" BASIS,
 11# WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
 12# See the License for the specific language governing permissions and
 13# limitations under the License.
 14
 15"""Statistics about MIP/LP models."""
 16
 17import dataclasses
 18import io
 19import math
 20from typing import Iterable, Optional
 21
 22from ortools.math_opt.python import model
 23
 24
 25@dataclasses.dataclass(frozen=True)
 26class Range:
 27    """A close range of values [min, max].
 28
 29    Attributes:
 30      minimum: The minimum value.
 31      maximum: The maximum value.
 32    """
 33
 34    minimum: float
 35    maximum: float
 36
 37
 38def merge_optional_ranges(
 39    lhs: Optional[Range], rhs: Optional[Range]
 40) -> Optional[Range]:
 41    """Merges the two optional ranges.
 42
 43    Args:
 44      lhs: The left hand side range.
 45      rhs: The right hand side range.
 46
 47    Returns:
 48      A merged range (None if both lhs and rhs are None).
 49    """
 50    if lhs is None:
 51        return rhs
 52    if rhs is None:
 53        return lhs
 54    return Range(
 55        minimum=min(lhs.minimum, rhs.minimum),
 56        maximum=max(lhs.maximum, rhs.maximum),
 57    )
 58
 59
 60def absolute_finite_non_zeros_range(values: Iterable[float]) -> Optional[Range]:
 61    """Returns the range of the absolute values of the finite non-zeros.
 62
 63    Args:
 64      values: An iterable object of float values.
 65
 66    Returns:
 67      The range of the absolute values of the finite non-zeros, None if no such
 68      value is found.
 69    """
 70    minimum: Optional[float] = None
 71    maximum: Optional[float] = None
 72    for v in values:
 73        v = abs(v)
 74        if math.isinf(v) or v == 0.0:
 75            continue
 76        if minimum is None:
 77            minimum = v
 78            maximum = v
 79        else:
 80            minimum = min(minimum, v)
 81            maximum = max(maximum, v)
 82
 83    assert (maximum is None) == (minimum is None), (minimum, maximum)
 84
 85    if minimum is None:
 86        return None
 87    return Range(minimum=minimum, maximum=maximum)
 88
 89
 90@dataclasses.dataclass(frozen=True)
 91class ModelRanges:
 92    """The ranges of the absolute values of the finite non-zero values in the model.
 93
 94    Each range is optional since there may be no finite non-zero values
 95    (e.g. empty model, empty objective, all variables unbounded, ...).
 96
 97    Attributes:
 98      objective_terms: The linear and quadratic objective terms (not including the
 99        offset).
100      variable_bounds: The variables' lower and upper bounds.
101      linear_constraint_bounds: The linear constraints' lower and upper bounds.
102      linear_constraint_coefficients: The coefficients of the variables in linear
103        constraints.
104    """
105
106    objective_terms: Optional[Range]
107    variable_bounds: Optional[Range]
108    linear_constraint_bounds: Optional[Range]
109    linear_constraint_coefficients: Optional[Range]
110
111    def __str__(self) -> str:
112        """Prints the ranges in scientific format with 2 digits (i.e.
113
114        f'{x:.2e}').
115
116        It returns a multi-line table list of ranges. The last line does NOT end
117        with a new line.
118
119        Returns:
120          The ranges in multiline string.
121        """
122        buf = io.StringIO()
123
124        def print_range(prefix: str, value: Optional[Range]) -> None:
125            buf.write(prefix)
126            if value is None:
127                buf.write("no finite values")
128                return
129            # Numbers are printed in scientific notation with a precision of 2. Since
130            # they are expected to be positive we can ignore the optional leading
131            # minus sign. We thus expects `d.dde[+-]dd(d)?` (the exponent is at least
132            # 2 digits but double can require 3 digits, with max +308 and min
133            # -308). Thus we can use a width of 9 to align the ranges properly.
134            buf.write(f"[{value.minimum:<9.2e}, {value.maximum:<9.2e}]")
135
136        print_range("Objective terms           : ", self.objective_terms)
137        print_range("\nVariable bounds           : ", self.variable_bounds)
138        print_range("\nLinear constraints bounds : ", self.linear_constraint_bounds)
139        print_range(
140            "\nLinear constraints coeffs : ", self.linear_constraint_coefficients
141        )
142        return buf.getvalue()
143
144
145def compute_model_ranges(mdl: model.Model) -> ModelRanges:
146    """Returns the ranges of the finite non-zero values in the given model.
147
148    Args:
149      mdl: The input model.
150
151    Returns:
152      The ranges of the finite non-zero values in the model.
153    """
154    return ModelRanges(
155        objective_terms=absolute_finite_non_zeros_range(
156            term.coefficient for term in mdl.objective.linear_terms()
157        ),
158        variable_bounds=merge_optional_ranges(
159            absolute_finite_non_zeros_range(v.lower_bound for v in mdl.variables()),
160            absolute_finite_non_zeros_range(v.upper_bound for v in mdl.variables()),
161        ),
162        linear_constraint_bounds=merge_optional_ranges(
163            absolute_finite_non_zeros_range(
164                c.lower_bound for c in mdl.linear_constraints()
165            ),
166            absolute_finite_non_zeros_range(
167                c.upper_bound for c in mdl.linear_constraints()
168            ),
169        ),
170        linear_constraint_coefficients=absolute_finite_non_zeros_range(
171            e.coefficient for e in mdl.linear_constraint_matrix_entries()
172        ),
173    )