ortools.math_opt.python.normalized_inequality

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