ortools.math_opt.python.normalized_inequality

  1# Copyright 2010-2025 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"""Data structures for linear and quadratic constraints.
 15
 16In contrast to BoundedLinearExpression and related structures, there is no
 17offset inside the inequality.
 18
 19This is not part of the MathOpt public API, do not depend on it externally.
 20"""
 21
 22import dataclasses
 23import math
 24from typing import Mapping, Optional, Union
 25
 26from ortools.math_opt.python import bounded_expressions
 27from ortools.math_opt.python import variables
 28
 29_BoundedLinearExpressions = (
 30    variables.LowerBoundedLinearExpression,
 31    variables.UpperBoundedLinearExpression,
 32    variables.BoundedLinearExpression,
 33)
 34
 35_BoundedQuadraticExpressions = (
 36    variables.LowerBoundedLinearExpression,
 37    variables.UpperBoundedLinearExpression,
 38    variables.BoundedLinearExpression,
 39    variables.LowerBoundedQuadraticExpression,
 40    variables.UpperBoundedQuadraticExpression,
 41    variables.BoundedQuadraticExpression,
 42)
 43
 44_BoundedExpressions = (
 45    bounded_expressions.LowerBoundedExpression,
 46    bounded_expressions.UpperBoundedExpression,
 47    bounded_expressions.BoundedExpression,
 48)
 49
 50
 51def _bool_error() -> TypeError:
 52    return TypeError(
 53        "Unsupported type for bounded_expr argument:"
 54        " bool. This error can occur when trying to add != constraints "
 55        "(which are not supported) or inequalities/equalities with constant "
 56        "left-hand-side and right-hand-side (which are redundant or make a "
 57        "model infeasible)."
 58    )
 59
 60
 61@dataclasses.dataclass
 62class NormalizedLinearInequality:
 63    """Represents an inequality lb <= expr <= ub where expr's offset is zero."""
 64
 65    lb: float
 66    ub: float
 67    coefficients: Mapping[variables.Variable, float]
 68
 69    def __init__(
 70        self,
 71        *,
 72        lb: Optional[float],
 73        ub: Optional[float],
 74        expr: Optional[variables.LinearTypes],
 75    ) -> None:
 76        """Raises a ValueError if expr's offset is infinite."""
 77        lb = -math.inf if lb is None else lb
 78        ub = math.inf if ub is None else ub
 79        expr = 0.0 if expr is None else expr
 80        if not isinstance(expr, (int, float, variables.LinearBase)):
 81            raise TypeError(
 82                f"Unsupported type for expr argument: {type(expr).__name__!r}."
 83            )
 84
 85        flat_expr = variables.as_flat_linear_expression(expr)
 86        if math.isinf(flat_expr.offset):
 87            raise ValueError(
 88                "Trying to create a linear constraint whose expression has an"
 89                " infinite offset."
 90            )
 91        self.lb = lb - flat_expr.offset
 92        self.ub = ub - flat_expr.offset
 93        self.coefficients = flat_expr.terms
 94
 95
 96def _normalize_bounded_linear_expression(
 97    bounded_expr: variables.BoundedLinearTypes,
 98) -> NormalizedLinearInequality:
 99    """Converts a bounded linear expression into a NormalizedLinearInequality."""
100    if isinstance(bounded_expr, variables.VarEqVar):
101        return NormalizedLinearInequality(
102            lb=0.0,
103            ub=0.0,
104            expr=bounded_expr.first_variable - bounded_expr.second_variable,
105        )
106    elif isinstance(bounded_expr, _BoundedExpressions):
107        if isinstance(bounded_expr.expression, (int, float, variables.LinearBase)):
108            return NormalizedLinearInequality(
109                lb=bounded_expr.lower_bound,
110                ub=bounded_expr.upper_bound,
111                expr=bounded_expr.expression,
112            )
113        else:
114            raise TypeError(
115                "Bad type of expression in bounded_expr:"
116                f" {type(bounded_expr.expression).__name__!r}."
117            )
118    else:
119        raise TypeError(f"bounded_expr has bad type: {type(bounded_expr).__name__!r}.")
120
121
122# TODO(b/227214976): Update the note below and link to pytype bug number.
123# Note: bounded_expr's type includes bool only as a workaround to a pytype
124# issue. Passing a bool for bounded_expr will raise an error in runtime.
125def as_normalized_linear_inequality(
126    bounded_expr: Optional[Union[bool, variables.BoundedLinearTypes]] = None,
127    *,
128    lb: Optional[float] = None,
129    ub: Optional[float] = None,
130    expr: Optional[variables.LinearTypes] = None,
131) -> NormalizedLinearInequality:
132    """Builds a NormalizedLinearInequality.
133
134    If bounded_expr is not None, then all other arguments must be None.
135
136    If expr has a nonzero offset, it will be subtracted from both lb and ub.
137
138    When bounded_expr is unset and a named argument is unset, we use the defaults:
139      * lb: -math.inf
140      * ub: math.inf
141      * expr: 0
142
143    Args:
144      bounded_expr: a linear inequality describing the constraint.
145      lb: The lower bound when bounded_expr is None.
146      ub: The upper bound if bounded_expr is None.
147      expr: The expression when bounded_expr is None.
148
149    Returns:
150      A NormalizedLinearInequality representing the linear constraint.
151    """
152    if isinstance(bounded_expr, bool):
153        raise _bool_error()
154    if bounded_expr is not None:
155        if lb is not None:
156            raise AssertionError(
157                "lb cannot be specified when bounded_expr is not None."
158            )
159        if ub is not None:
160            raise AssertionError(
161                "ub cannot be specified when bounded_expr is not None."
162            )
163        if expr is not None:
164            raise AssertionError(
165                "expr cannot be specified when bounded_expr is not None"
166            )
167        return _normalize_bounded_linear_expression(bounded_expr)
168    # Note: NormalizedLinearInequality() will runtime check the type of expr.
169    return NormalizedLinearInequality(lb=lb, ub=ub, expr=expr)
170
171
172@dataclasses.dataclass
173class NormalizedQuadraticInequality:
174    """Represents an inequality lb <= expr <= ub where expr's offset is zero."""
175
176    lb: float
177    ub: float
178    linear_coefficients: Mapping[variables.Variable, float]
179    quadratic_coefficients: Mapping[variables.QuadraticTermKey, float]
180
181    def __init__(
182        self,
183        *,
184        lb: Optional[float] = None,
185        ub: Optional[float] = None,
186        expr: Optional[variables.QuadraticTypes] = None,
187    ) -> None:
188        """Raises a ValueError if expr's offset is infinite."""
189        lb = -math.inf if lb is None else lb
190        ub = math.inf if ub is None else ub
191        expr = 0.0 if expr is None else expr
192        if not isinstance(
193            expr, (int, float, variables.LinearBase, variables.QuadraticBase)
194        ):
195            raise TypeError(
196                f"Unsupported type for expr argument: {type(expr).__name__!r}."
197            )
198        flat_expr = variables.as_flat_quadratic_expression(expr)
199        if math.isinf(flat_expr.offset):
200            raise ValueError(
201                "Trying to create a quadratic constraint whose expression has an"
202                " infinite offset."
203            )
204        self.lb = lb - flat_expr.offset
205        self.ub = ub - flat_expr.offset
206        self.linear_coefficients = flat_expr.linear_terms
207        self.quadratic_coefficients = flat_expr.quadratic_terms
208
209
210def _normalize_bounded_quadratic_expression(
211    bounded_expr: Union[variables.BoundedQuadraticTypes, variables.BoundedLinearTypes],
212) -> NormalizedQuadraticInequality:
213    """Converts a bounded quadratic expression into a NormalizedQuadraticInequality."""
214    if isinstance(bounded_expr, variables.VarEqVar):
215        return NormalizedQuadraticInequality(
216            lb=0.0,
217            ub=0.0,
218            expr=bounded_expr.first_variable - bounded_expr.second_variable,
219        )
220    elif isinstance(bounded_expr, _BoundedExpressions):
221        if isinstance(
222            bounded_expr.expression,
223            (int, float, variables.LinearBase, variables.QuadraticBase),
224        ):
225            return NormalizedQuadraticInequality(
226                lb=bounded_expr.lower_bound,
227                ub=bounded_expr.upper_bound,
228                expr=bounded_expr.expression,
229            )
230        else:
231            raise TypeError(
232                "bounded_expr.expression has bad type:"
233                f" {type(bounded_expr.expression).__name__!r}."
234            )
235    else:
236        raise TypeError(f"bounded_expr has bad type: {type(bounded_expr).__name__!r}.")
237
238
239# TODO(b/227214976): Update the note below and link to pytype bug number.
240# Note: bounded_expr's type includes bool only as a workaround to a pytype
241# issue. Passing a bool for bounded_expr will raise an error in runtime.
242def as_normalized_quadratic_inequality(
243    bounded_expr: Optional[
244        Union[bool, variables.BoundedLinearTypes, variables.BoundedQuadraticTypes]
245    ] = None,
246    *,
247    lb: Optional[float] = None,
248    ub: Optional[float] = None,
249    expr: Optional[variables.QuadraticTypes] = None,
250) -> NormalizedQuadraticInequality:
251    """Builds a NormalizedLinearInequality.
252
253    If bounded_expr is not None, then all other arguments must be None.
254
255    If expr has a nonzero offset, it will be subtracted from both lb and ub.
256
257    When bounded_expr is unset and a named argument is unset, we use the defaults:
258      * lb: -math.inf
259      * ub: math.inf
260      * expr: 0
261
262    Args:
263      bounded_expr: a quadratic inequality describing the constraint.
264      lb: The lower bound when bounded_expr is None.
265      ub: The upper bound if bounded_expr is None.
266      expr: The expression when bounded_expr is None.
267
268    Returns:
269      A NormalizedLinearInequality representing the linear constraint.
270    """
271    if isinstance(bounded_expr, bool):
272        raise _bool_error()
273    if bounded_expr is not None:
274        if lb is not None:
275            raise AssertionError(
276                "lb cannot be specified when bounded_expr is not None."
277            )
278        if ub is not None:
279            raise AssertionError(
280                "ub cannot be specified when bounded_expr is not None."
281            )
282        if expr is not None:
283            raise AssertionError(
284                "expr cannot be specified when bounded_expr is not None"
285            )
286        return _normalize_bounded_quadratic_expression(bounded_expr)
287    return NormalizedQuadraticInequality(lb=lb, ub=ub, expr=expr)