ortools.math_opt.python.statistics

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