ortools.math_opt.python.variables

   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"""Define Variables and Linear Expressions."""
  15
  16import abc
  17import collections
  18import dataclasses
  19import math
  20import typing
  21from typing import (
  22    Any,
  23    DefaultDict,
  24    Deque,
  25    Generic,
  26    Iterable,
  27    Mapping,
  28    NoReturn,
  29    Optional,
  30    Protocol,
  31    Tuple,
  32    Type,
  33    TypeVar,
  34    Union,
  35)
  36
  37import immutabledict
  38
  39from ortools.math_opt.elemental.python import enums
  40from ortools.math_opt.python import bounded_expressions
  41from ortools.math_opt.python import from_model
  42from ortools.math_opt.python.elemental import elemental
  43
  44
  45LinearTypes = Union[int, float, "LinearBase"]
  46QuadraticTypes = Union[int, float, "LinearBase", "QuadraticBase"]
  47LinearTypesExceptVariable = Union[
  48    float, int, "LinearTerm", "LinearExpression", "LinearSum", "LinearProduct"
  49]
  50
  51
  52_EXPRESSION_COMP_EXPRESSION_MESSAGE = (
  53    "This error can occur when adding "
  54    "inequalities of the form `(a <= b) <= "
  55    "c` where (a, b, c) includes two or more"
  56    " non-constant linear expressions"
  57)
  58
  59
  60def _raise_binary_operator_type_error(
  61    operator: str,
  62    lhs: Type[Any],
  63    rhs: Type[Any],
  64    extra_message: Optional[str] = None,
  65) -> NoReturn:
  66    """Raises TypeError on unsupported operators."""
  67    message = (
  68        f"unsupported operand type(s) for {operator}: {lhs.__name__!r} and"
  69        f" {rhs.__name__!r}"
  70    )
  71    if extra_message is not None:
  72        message += "\n" + extra_message
  73    raise TypeError(message)
  74
  75
  76def _raise_ne_not_supported() -> NoReturn:
  77    raise TypeError("!= constraints are not supported")
  78
  79
  80LowerBoundedLinearExpression = bounded_expressions.LowerBoundedExpression["LinearBase"]
  81UpperBoundedLinearExpression = bounded_expressions.UpperBoundedExpression["LinearBase"]
  82BoundedLinearExpression = bounded_expressions.BoundedExpression["LinearBase"]
  83
  84
  85class VarEqVar:
  86    """The result of the equality comparison between two Variable.
  87
  88    We use an object here to delay the evaluation of equality so that we can use
  89    the operator== in two use-cases:
  90
  91      1. when the user want to test that two Variable values references the same
  92         variable. This is supported by having this object support implicit
  93         conversion to bool.
  94
  95      2. when the user want to use the equality to create a constraint of equality
  96         between two variables.
  97    """
  98
  99    __slots__ = "_first_variable", "_second_variable"
 100
 101    def __init__(
 102        self,
 103        first_variable: "Variable",
 104        second_variable: "Variable",
 105    ) -> None:
 106        self._first_variable: "Variable" = first_variable
 107        self._second_variable: "Variable" = second_variable
 108
 109    @property
 110    def first_variable(self) -> "Variable":
 111        return self._first_variable
 112
 113    @property
 114    def second_variable(self) -> "Variable":
 115        return self._second_variable
 116
 117    def __bool__(self) -> bool:
 118        return (
 119            self._first_variable.elemental is self._second_variable.elemental
 120            and self._first_variable.id == self._second_variable.id
 121        )
 122
 123    def __str__(self):
 124        return f"{self.first_variable!s} == {self._second_variable!s}"
 125
 126    def __repr__(self):
 127        return f"{self.first_variable!r} == {self._second_variable!r}"
 128
 129
 130BoundedLinearTypesList = (
 131    LowerBoundedLinearExpression,
 132    UpperBoundedLinearExpression,
 133    BoundedLinearExpression,
 134    VarEqVar,
 135)
 136BoundedLinearTypes = Union[BoundedLinearTypesList]
 137
 138LowerBoundedQuadraticExpression = bounded_expressions.LowerBoundedExpression[
 139    "QuadraticBase"
 140]
 141UpperBoundedQuadraticExpression = bounded_expressions.UpperBoundedExpression[
 142    "QuadraticBase"
 143]
 144BoundedQuadraticExpression = bounded_expressions.BoundedExpression["QuadraticBase"]
 145
 146BoundedQuadraticTypesList = (
 147    LowerBoundedQuadraticExpression,
 148    UpperBoundedQuadraticExpression,
 149    BoundedQuadraticExpression,
 150)
 151BoundedQuadraticTypes = Union[BoundedQuadraticTypesList]
 152
 153
 154# TODO(b/231426528): consider using a frozen dataclass.
 155class QuadraticTermKey:
 156    """An id-ordered pair of variables used as a key for quadratic terms."""
 157
 158    __slots__ = "_first_var", "_second_var"
 159
 160    def __init__(self, a: "Variable", b: "Variable"):
 161        """Variables a and b will be ordered internally by their ids."""
 162        self._first_var: "Variable" = a
 163        self._second_var: "Variable" = b
 164        if self._first_var.id > self._second_var.id:
 165            self._first_var, self._second_var = self._second_var, self._first_var
 166
 167    @property
 168    def first_var(self) -> "Variable":
 169        return self._first_var
 170
 171    @property
 172    def second_var(self) -> "Variable":
 173        return self._second_var
 174
 175    def __eq__(self, other: "QuadraticTermKey") -> bool:
 176        return bool(
 177            self._first_var == other._first_var
 178            and self._second_var == other._second_var
 179        )
 180
 181    def __hash__(self) -> int:
 182        return hash((self._first_var, self._second_var))
 183
 184    def __str__(self):
 185        return f"{self._first_var!s} * {self._second_var!s}"
 186
 187    def __repr__(self):
 188        return f"QuadraticTermKey({self._first_var!r}, {self._second_var!r})"
 189
 190
 191@dataclasses.dataclass
 192class _ProcessedElements:
 193    """Auxiliary data class for LinearBase._flatten_once_and_add_to()."""
 194
 195    terms: DefaultDict["Variable", float] = dataclasses.field(
 196        default_factory=lambda: collections.defaultdict(float)
 197    )
 198    offset: float = 0.0
 199
 200
 201@dataclasses.dataclass
 202class _QuadraticProcessedElements(_ProcessedElements):
 203    """Auxiliary data class for QuadraticBase._quadratic_flatten_once_and_add_to()."""
 204
 205    quadratic_terms: DefaultDict["QuadraticTermKey", float] = dataclasses.field(
 206        default_factory=lambda: collections.defaultdict(float)
 207    )
 208
 209
 210class _ToProcessElements(Protocol):
 211    """Auxiliary to-process stack interface for LinearBase._flatten_once_and_add_to() and QuadraticBase._quadratic_flatten_once_and_add_to()."""
 212
 213    __slots__ = ()
 214
 215    def append(self, term: "LinearBase", scale: float) -> None:
 216        """Add a linear object and scale to the to-process stack."""
 217
 218
 219_T = TypeVar("_T", "LinearBase", Union["LinearBase", "QuadraticBase"])
 220
 221
 222class _ToProcessElementsImplementation(Generic[_T]):
 223    """Auxiliary data class for LinearBase._flatten_once_and_add_to()."""
 224
 225    __slots__ = ("_queue",)
 226
 227    def __init__(self, term: _T, scale: float) -> None:
 228        self._queue: Deque[Tuple[_T, float]] = collections.deque([(term, scale)])
 229
 230    def append(self, term: _T, scale: float) -> None:
 231        self._queue.append((term, scale))
 232
 233    def pop(self) -> Tuple[_T, float]:
 234        return self._queue.popleft()
 235
 236    def __bool__(self) -> bool:
 237        return bool(self._queue)
 238
 239
 240_LinearToProcessElements = _ToProcessElementsImplementation["LinearBase"]
 241_QuadraticToProcessElements = _ToProcessElementsImplementation[
 242    Union["LinearBase", "QuadraticBase"]
 243]
 244
 245
 246class LinearBase(metaclass=abc.ABCMeta):
 247    """Interface for types that can build linear expressions with +, -, * and /.
 248
 249    Classes derived from LinearBase (plus float and int scalars) are used to
 250    build expression trees describing a linear expression. Operations nodes of the
 251    expression tree include:
 252
 253      * LinearSum: describes a deferred sum of LinearTypes objects.
 254      * LinearProduct: describes a deferred product of a scalar and a
 255        LinearTypes object.
 256
 257    Leaf nodes of the expression tree include:
 258
 259      * float and int scalars.
 260      * Variable: a single variable.
 261      * LinearTerm: the product of a scalar and a Variable object.
 262      * LinearExpression: the sum of a scalar and LinearTerm objects.
 263
 264    LinearBase objects/expression-trees can be used directly to create
 265    constraints or objective functions. However, to facilitate their inspection,
 266    any LinearTypes object can be flattened to a LinearExpression
 267    through:
 268
 269     as_flat_linear_expression(value: LinearTypes) -> LinearExpression:
 270
 271    In addition, all LinearBase objects are immutable.
 272
 273    Performance notes:
 274
 275    Using an expression tree representation instead of an eager construction of
 276    LinearExpression objects reduces known inefficiencies associated with the
 277    use of operator overloading to construct linear expressions. In particular, we
 278    expect the runtime of as_flat_linear_expression() to be linear in the size of
 279    the expression tree. Additional performance can gained by using LinearSum(c)
 280    instead of sum(c) for a container c, as the latter creates len(c) LinearSum
 281    objects.
 282    """
 283
 284    __slots__ = ()
 285
 286    # TODO(b/216492143): explore requirements for this function so calculation of
 287    # coefficients and offsets follow expected associativity rules (so approximate
 288    # float calculations are as expected).
 289    # TODO(b/216492143): add more details of what subclasses need to do in
 290    # developers guide.
 291    @abc.abstractmethod
 292    def _flatten_once_and_add_to(
 293        self,
 294        scale: float,
 295        processed_elements: _ProcessedElements,
 296        target_stack: _ToProcessElements,
 297    ) -> None:
 298        """Flatten one level of tree if needed and add to targets.
 299
 300        Classes derived from LinearBase only need to implement this function
 301        to enable transformation to LinearExpression through
 302        as_flat_linear_expression().
 303
 304        Args:
 305          scale: multiply elements by this number when processing or adding to
 306            stack.
 307          processed_elements: where to add LinearTerms and scalars that can be
 308            processed immediately.
 309          target_stack: where to add LinearBase elements that are not scalars or
 310            LinearTerms (i.e. elements that need further flattening).
 311            Implementations should append() to this stack to avoid being recursive.
 312        """
 313
 314    def __eq__(
 315        self, rhs: LinearTypes
 316    ) -> (
 317        BoundedLinearExpression
 318    ):  # pytype: disable=signature-mismatch  # overriding-return-type-checks
 319        # Note: when rhs is a QuadraticBase, this will cause rhs.__eq__(self) to be
 320        # invoked, which is defined.
 321        if isinstance(rhs, QuadraticBase):
 322            return NotImplemented
 323        if isinstance(rhs, (int, float)):
 324            return BoundedLinearExpression(rhs, self, rhs)
 325        if not isinstance(rhs, LinearBase):
 326            _raise_binary_operator_type_error("==", type(self), type(rhs))
 327        return BoundedLinearExpression(0.0, self - rhs, 0.0)
 328
 329    def __ne__(
 330        self, rhs: LinearTypes
 331    ) -> (
 332        NoReturn
 333    ):  # pytype: disable=signature-mismatch  # overriding-return-type-checks
 334        _raise_ne_not_supported()
 335
 336    @typing.overload
 337    def __le__(self, rhs: float) -> "UpperBoundedLinearExpression": ...
 338
 339    @typing.overload
 340    def __le__(self, rhs: "LinearBase") -> "BoundedLinearExpression": ...
 341
 342    @typing.overload
 343    def __le__(self, rhs: "BoundedLinearExpression") -> NoReturn: ...
 344
 345    def __le__(self, rhs):
 346        # Note: when rhs is a QuadraticBase, this will cause rhs.__ge__(self) to be
 347        # invoked, which is defined.
 348        if isinstance(rhs, QuadraticBase):
 349            return NotImplemented
 350        if isinstance(rhs, (int, float)):
 351            return UpperBoundedLinearExpression(self, rhs)
 352        if isinstance(rhs, LinearBase):
 353            return BoundedLinearExpression(-math.inf, self - rhs, 0.0)
 354        if isinstance(rhs, bounded_expressions.BoundedExpression):
 355            _raise_binary_operator_type_error(
 356                "<=", type(self), type(rhs), _EXPRESSION_COMP_EXPRESSION_MESSAGE
 357            )
 358        _raise_binary_operator_type_error("<=", type(self), type(rhs))
 359
 360    @typing.overload
 361    def __ge__(self, lhs: float) -> "LowerBoundedLinearExpression": ...
 362
 363    @typing.overload
 364    def __ge__(self, lhs: "LinearBase") -> "BoundedLinearExpression": ...
 365
 366    @typing.overload
 367    def __ge__(self, lhs: "BoundedLinearExpression") -> NoReturn: ...
 368
 369    def __ge__(self, lhs):
 370        # Note: when lhs is a QuadraticBase, this will cause lhs.__le__(self) to be
 371        # invoked, which is defined.
 372        if isinstance(lhs, QuadraticBase):
 373            return NotImplemented
 374        if isinstance(lhs, (int, float)):
 375            return LowerBoundedLinearExpression(self, lhs)
 376        if isinstance(lhs, LinearBase):
 377            return BoundedLinearExpression(0.0, self - lhs, math.inf)
 378        if isinstance(lhs, bounded_expressions.BoundedExpression):
 379            _raise_binary_operator_type_error(
 380                ">=", type(self), type(lhs), _EXPRESSION_COMP_EXPRESSION_MESSAGE
 381            )
 382        _raise_binary_operator_type_error(">=", type(self), type(lhs))
 383
 384    def __add__(self, expr: LinearTypes) -> "LinearSum":
 385        if not isinstance(expr, (int, float, LinearBase)):
 386            return NotImplemented
 387        return LinearSum((self, expr))
 388
 389    def __radd__(self, expr: LinearTypes) -> "LinearSum":
 390        if not isinstance(expr, (int, float, LinearBase)):
 391            return NotImplemented
 392        return LinearSum((expr, self))
 393
 394    def __sub__(self, expr: LinearTypes) -> "LinearSum":
 395        if not isinstance(expr, (int, float, LinearBase)):
 396            return NotImplemented
 397        return LinearSum((self, -expr))
 398
 399    def __rsub__(self, expr: LinearTypes) -> "LinearSum":
 400        if not isinstance(expr, (int, float, LinearBase, QuadraticBase)):
 401            return NotImplemented
 402        return LinearSum((expr, -self))
 403
 404    @typing.overload
 405    def __mul__(self, other: float) -> "LinearProduct": ...
 406
 407    @typing.overload
 408    def __mul__(self, other: "LinearBase") -> "LinearLinearProduct": ...
 409
 410    def __mul__(self, other):
 411        if not isinstance(other, (int, float, LinearBase)):
 412            return NotImplemented
 413        if isinstance(other, LinearBase):
 414            return LinearLinearProduct(self, other)
 415        return LinearProduct(other, self)
 416
 417    def __rmul__(self, constant: float) -> "LinearProduct":
 418        if not isinstance(constant, (int, float)):
 419            return NotImplemented
 420        return LinearProduct(constant, self)
 421
 422    # TODO(b/216492143): explore numerical consequences of 1.0 / constant below.
 423    def __truediv__(self, constant: float) -> "LinearProduct":
 424        if not isinstance(constant, (int, float)):
 425            return NotImplemented
 426        return LinearProduct(1.0 / constant, self)
 427
 428    def __neg__(self) -> "LinearProduct":
 429        return LinearProduct(-1.0, self)
 430
 431
 432class QuadraticBase(metaclass=abc.ABCMeta):
 433    """Interface for types that can build quadratic expressions with +, -, * and /.
 434
 435    Classes derived from QuadraticBase and LinearBase (plus float and int scalars)
 436    are used to build expression trees describing a quadratic expression.
 437    Operations nodes of the expression tree include:
 438
 439        * QuadraticSum: describes a deferred sum of QuadraticTypes objects.
 440        * QuadraticProduct: describes a deferred product of a scalar and a
 441          QuadraticTypes object.
 442        * LinearLinearProduct: describes a deferred product of two LinearTypes
 443          objects.
 444
 445      Leaf nodes of the expression tree include:
 446
 447        * float and int scalars.
 448        * Variable: a single variable.
 449        * LinearTerm: the product of a scalar and a Variable object.
 450        * LinearExpression: the sum of a scalar and LinearTerm objects.
 451        * QuadraticTerm: the product of a scalar and two Variable objects.
 452        * QuadraticExpression: the sum of a scalar, LinearTerm objects and
 453          QuadraticTerm objects.
 454
 455    QuadraticBase objects/expression-trees can be used directly to create
 456    objective functions. However, to facilitate their inspection, any
 457    QuadraticTypes object can be flattened to a QuadraticExpression
 458    through:
 459
 460     as_flat_quadratic_expression(value: QuadraticTypes) -> QuadraticExpression:
 461
 462    In addition, all QuadraticBase objects are immutable.
 463
 464    Performance notes:
 465
 466    Using an expression tree representation instead of an eager construction of
 467    QuadraticExpression objects reduces known inefficiencies associated with the
 468    use of operator overloading to construct quadratic expressions. In particular,
 469    we expect the runtime of as_flat_quadratic_expression() to be linear in the
 470    size of the expression tree. Additional performance can gained by using
 471    QuadraticSum(c) instead of sum(c) for a container c, as the latter creates
 472    len(c) QuadraticSum objects.
 473    """
 474
 475    __slots__ = ()
 476
 477    # TODO(b/216492143): explore requirements for this function so calculation of
 478    # coefficients and offsets follow expected associativity rules (so approximate
 479    # float calculations are as expected).
 480    # TODO(b/216492143): add more details of what subclasses need to do in
 481    # developers guide.
 482    @abc.abstractmethod
 483    def _quadratic_flatten_once_and_add_to(
 484        self,
 485        scale: float,
 486        processed_elements: _QuadraticProcessedElements,
 487        target_stack: _QuadraticToProcessElements,
 488    ) -> None:
 489        """Flatten one level of tree if needed and add to targets.
 490
 491        Classes derived from QuadraticBase only need to implement this function
 492        to enable transformation to QuadraticExpression through
 493        as_flat_quadratic_expression().
 494
 495        Args:
 496          scale: multiply elements by this number when processing or adding to
 497            stack.
 498          processed_elements: where to add linear terms, quadratic terms and scalars
 499            that can be processed immediately.
 500          target_stack: where to add LinearBase and QuadraticBase elements that are
 501            not scalars or linear terms or quadratic terms (i.e. elements that need
 502            further flattening). Implementations should append() to this stack to
 503            avoid being recursive.
 504        """
 505
 506    def __eq__(
 507        self, rhs: QuadraticTypes
 508    ) -> (
 509        BoundedQuadraticExpression
 510    ):  # pytype: disable=signature-mismatch  # overriding-return-type-checks
 511        if isinstance(rhs, (int, float)):
 512            return BoundedQuadraticExpression(rhs, self, rhs)
 513        if not isinstance(rhs, (LinearBase, QuadraticBase)):
 514            _raise_binary_operator_type_error("==", type(self), type(rhs))
 515        return BoundedQuadraticExpression(0.0, self - rhs, 0.0)
 516
 517    def __ne__(
 518        self, rhs: QuadraticTypes
 519    ) -> (
 520        NoReturn
 521    ):  # pytype: disable=signature-mismatch  # overriding-return-type-checks
 522        _raise_ne_not_supported()
 523
 524    @typing.overload
 525    def __le__(self, rhs: float) -> UpperBoundedQuadraticExpression: ...
 526
 527    @typing.overload
 528    def __le__(
 529        self, rhs: Union[LinearBase, "QuadraticBase"]
 530    ) -> BoundedQuadraticExpression: ...
 531
 532    @typing.overload
 533    def __le__(self, rhs: BoundedQuadraticExpression) -> NoReturn: ...
 534
 535    def __le__(self, rhs):
 536        if isinstance(rhs, (int, float)):
 537            return UpperBoundedQuadraticExpression(self, rhs)
 538        if isinstance(rhs, (LinearBase, QuadraticBase)):
 539            return BoundedQuadraticExpression(-math.inf, self - rhs, 0.0)
 540        if isinstance(rhs, bounded_expressions.BoundedExpression):
 541            _raise_binary_operator_type_error(
 542                "<=", type(self), type(rhs), _EXPRESSION_COMP_EXPRESSION_MESSAGE
 543            )
 544        _raise_binary_operator_type_error("<=", type(self), type(rhs))
 545
 546    @typing.overload
 547    def __ge__(self, lhs: float) -> LowerBoundedQuadraticExpression: ...
 548
 549    @typing.overload
 550    def __ge__(
 551        self, lhs: Union[LinearBase, "QuadraticBase"]
 552    ) -> BoundedQuadraticExpression: ...
 553
 554    @typing.overload
 555    def __ge__(self, lhs: BoundedQuadraticExpression) -> NoReturn: ...
 556
 557    def __ge__(self, lhs):
 558        if isinstance(lhs, (int, float)):
 559            return LowerBoundedQuadraticExpression(self, lhs)
 560        if isinstance(lhs, (LinearBase, QuadraticBase)):
 561            return BoundedQuadraticExpression(0.0, self - lhs, math.inf)
 562        if isinstance(lhs, bounded_expressions.BoundedExpression):
 563            _raise_binary_operator_type_error(
 564                ">=", type(self), type(lhs), _EXPRESSION_COMP_EXPRESSION_MESSAGE
 565            )
 566        _raise_binary_operator_type_error(">=", type(self), type(lhs))
 567
 568    def __add__(self, expr: QuadraticTypes) -> "QuadraticSum":
 569        if not isinstance(expr, (int, float, LinearBase, QuadraticBase)):
 570            return NotImplemented
 571        return QuadraticSum((self, expr))
 572
 573    def __radd__(self, expr: QuadraticTypes) -> "QuadraticSum":
 574        if not isinstance(expr, (int, float, LinearBase, QuadraticBase)):
 575            return NotImplemented
 576        return QuadraticSum((expr, self))
 577
 578    def __sub__(self, expr: QuadraticTypes) -> "QuadraticSum":
 579        if not isinstance(expr, (int, float, LinearBase, QuadraticBase)):
 580            return NotImplemented
 581        return QuadraticSum((self, -expr))
 582
 583    def __rsub__(self, expr: QuadraticTypes) -> "QuadraticSum":
 584        if not isinstance(expr, (int, float, LinearBase, QuadraticBase)):
 585            return NotImplemented
 586        return QuadraticSum((expr, -self))
 587
 588    def __mul__(self, other: float) -> "QuadraticProduct":
 589        if not isinstance(other, (int, float)):
 590            return NotImplemented
 591        return QuadraticProduct(other, self)
 592
 593    def __rmul__(self, other: float) -> "QuadraticProduct":
 594        if not isinstance(other, (int, float)):
 595            return NotImplemented
 596        return QuadraticProduct(other, self)
 597
 598    # TODO(b/216492143): explore numerical consequences of 1.0 / constant below.
 599    def __truediv__(self, constant: float) -> "QuadraticProduct":
 600        if not isinstance(constant, (int, float)):
 601            return NotImplemented
 602        return QuadraticProduct(1.0 / constant, self)
 603
 604    def __neg__(self) -> "QuadraticProduct":
 605        return QuadraticProduct(-1.0, self)
 606
 607
 608class Variable(LinearBase, from_model.FromModel):
 609    """A decision variable for an optimization model.
 610
 611    A decision variable takes a value from a domain, either the real numbers or
 612    the integers, and restricted to be in some interval [lb, ub] (where lb and ub
 613    can be infinite). The case of lb == ub is allowed, this means the variable
 614    must take a single value. The case of lb > ub is also allowed, this implies
 615    that the problem is infeasible.
 616
 617    A Variable is configured as follows:
 618      * lower_bound: a float property, lb above. Should not be NaN nor +inf.
 619      * upper_bound: a float property, ub above. Should not be NaN nor -inf.
 620      * integer: a bool property, if the domain is integer or continuous.
 621
 622    The name is optional, read only, and used only for debugging. Non-empty names
 623    should be distinct.
 624
 625    Every Variable is associated with a Model (defined below). Note that data
 626    describing the variable (e.g. lower_bound) is owned by Model.storage, this
 627    class is simply a reference to that data. Do not create a Variable directly,
 628    use Model.add_variable() instead.
 629    """
 630
 631    __slots__ = "_elemental", "_id"
 632
 633    def __init__(self, elem: elemental.Elemental, vid: int) -> None:
 634        """Internal only, prefer Model functions (add_variable() and get_variable())."""
 635        if not isinstance(vid, int):
 636            raise TypeError(f"vid type should be int, was:{type(vid)}")
 637        self._elemental: elemental.Elemental = elem
 638        self._id: int = vid
 639
 640    @property
 641    def lower_bound(self) -> float:
 642        return self._elemental.get_attr(
 643            enums.DoubleAttr1.VARIABLE_LOWER_BOUND, (self._id,)
 644        )
 645
 646    @lower_bound.setter
 647    def lower_bound(self, value: float) -> None:
 648        self._elemental.set_attr(
 649            enums.DoubleAttr1.VARIABLE_LOWER_BOUND,
 650            (self._id,),
 651            value,
 652        )
 653
 654    @property
 655    def upper_bound(self) -> float:
 656        return self._elemental.get_attr(
 657            enums.DoubleAttr1.VARIABLE_UPPER_BOUND, (self._id,)
 658        )
 659
 660    @upper_bound.setter
 661    def upper_bound(self, value: float) -> None:
 662        self._elemental.set_attr(
 663            enums.DoubleAttr1.VARIABLE_UPPER_BOUND,
 664            (self._id,),
 665            value,
 666        )
 667
 668    @property
 669    def integer(self) -> bool:
 670        return self._elemental.get_attr(enums.BoolAttr1.VARIABLE_INTEGER, (self._id,))
 671
 672    @integer.setter
 673    def integer(self, value: bool) -> None:
 674        self._elemental.set_attr(enums.BoolAttr1.VARIABLE_INTEGER, (self._id,), value)
 675
 676    @property
 677    def name(self) -> str:
 678        return self._elemental.get_element_name(enums.ElementType.VARIABLE, self._id)
 679
 680    @property
 681    def id(self) -> int:
 682        return self._id
 683
 684    @property
 685    def elemental(self) -> elemental.Elemental:
 686        """Internal use only."""
 687        return self._elemental
 688
 689    def __str__(self):
 690        """Returns the name, or a string containing the id if the name is empty."""
 691        return self.name if self.name else f"variable_{self.id}"
 692
 693    def __repr__(self):
 694        return f"<Variable id: {self.id}, name: {self.name!r}>"
 695
 696    @typing.overload
 697    def __eq__(self, rhs: "Variable") -> "VarEqVar": ...
 698
 699    @typing.overload
 700    def __eq__(self, rhs: LinearTypesExceptVariable) -> "BoundedLinearExpression": ...
 701
 702    def __eq__(self, rhs):
 703        if isinstance(rhs, Variable):
 704            return VarEqVar(self, rhs)
 705        return super().__eq__(rhs)
 706
 707    @typing.overload
 708    def __ne__(self, rhs: "Variable") -> bool: ...
 709
 710    @typing.overload
 711    def __ne__(self, rhs: LinearTypesExceptVariable) -> NoReturn: ...
 712
 713    def __ne__(self, rhs):
 714        if isinstance(rhs, Variable):
 715            return not self == rhs
 716        _raise_ne_not_supported()
 717
 718    def __hash__(self) -> int:
 719        return hash(self._id)
 720
 721    @typing.overload
 722    def __mul__(self, other: float) -> "LinearTerm": ...
 723
 724    @typing.overload
 725    def __mul__(self, other: Union["Variable", "LinearTerm"]) -> "QuadraticTerm": ...
 726
 727    @typing.overload
 728    def __mul__(self, other: "LinearBase") -> "LinearLinearProduct": ...
 729
 730    def __mul__(self, other):
 731        if not isinstance(other, (int, float, LinearBase)):
 732            return NotImplemented
 733        if isinstance(other, Variable):
 734            return QuadraticTerm(QuadraticTermKey(self, other), 1.0)
 735        if isinstance(other, LinearTerm):
 736            return QuadraticTerm(
 737                QuadraticTermKey(self, other.variable), other.coefficient
 738            )
 739        if isinstance(other, LinearBase):
 740            return LinearLinearProduct(self, other)  # pytype: disable=bad-return-type
 741        return LinearTerm(self, other)
 742
 743    def __rmul__(self, constant: float) -> "LinearTerm":
 744        if not isinstance(constant, (int, float)):
 745            return NotImplemented
 746        return LinearTerm(self, constant)
 747
 748    # TODO(b/216492143): explore numerical consequences of 1.0 / constant below.
 749    def __truediv__(self, constant: float) -> "LinearTerm":
 750        if not isinstance(constant, (int, float)):
 751            return NotImplemented
 752        return LinearTerm(self, 1.0 / constant)
 753
 754    def __neg__(self) -> "LinearTerm":
 755        return LinearTerm(self, -1.0)
 756
 757    def _flatten_once_and_add_to(
 758        self,
 759        scale: float,
 760        processed_elements: _ProcessedElements,
 761        target_stack: _ToProcessElements,
 762    ) -> None:
 763        processed_elements.terms[self] += scale
 764
 765
 766class LinearTerm(LinearBase):
 767    """The product of a scalar and a variable.
 768
 769    This class is immutable.
 770    """
 771
 772    __slots__ = "_variable", "_coefficient"
 773
 774    def __init__(self, variable: Variable, coefficient: float) -> None:
 775        self._variable: Variable = variable
 776        self._coefficient: float = coefficient
 777
 778    @property
 779    def variable(self) -> Variable:
 780        return self._variable
 781
 782    @property
 783    def coefficient(self) -> float:
 784        return self._coefficient
 785
 786    def _flatten_once_and_add_to(
 787        self,
 788        scale: float,
 789        processed_elements: _ProcessedElements,
 790        target_stack: _ToProcessElements,
 791    ) -> None:
 792        processed_elements.terms[self._variable] += self._coefficient * scale
 793
 794    @typing.overload
 795    def __mul__(self, other: float) -> "LinearTerm": ...
 796
 797    @typing.overload
 798    def __mul__(self, other: Union["Variable", "LinearTerm"]) -> "QuadraticTerm": ...
 799
 800    @typing.overload
 801    def __mul__(self, other: "LinearBase") -> "LinearLinearProduct": ...
 802
 803    def __mul__(self, other):
 804        if not isinstance(other, (int, float, LinearBase)):
 805            return NotImplemented
 806        if isinstance(other, Variable):
 807            return QuadraticTerm(
 808                QuadraticTermKey(self._variable, other), self._coefficient
 809            )
 810        if isinstance(other, LinearTerm):
 811            return QuadraticTerm(
 812                QuadraticTermKey(self.variable, other.variable),
 813                self._coefficient * other.coefficient,
 814            )
 815        if isinstance(other, LinearBase):
 816            return LinearLinearProduct(self, other)  # pytype: disable=bad-return-type
 817        return LinearTerm(self._variable, self._coefficient * other)
 818
 819    def __rmul__(self, constant: float) -> "LinearTerm":
 820        if not isinstance(constant, (int, float)):
 821            return NotImplemented
 822        return LinearTerm(self._variable, self._coefficient * constant)
 823
 824    def __truediv__(self, constant: float) -> "LinearTerm":
 825        if not isinstance(constant, (int, float)):
 826            return NotImplemented
 827        return LinearTerm(self._variable, self._coefficient / constant)
 828
 829    def __neg__(self) -> "LinearTerm":
 830        return LinearTerm(self._variable, -self._coefficient)
 831
 832    def __str__(self):
 833        return f"{self._coefficient} * {self._variable}"
 834
 835    def __repr__(self):
 836        return f"LinearTerm({self._variable!r}, {self._coefficient!r})"
 837
 838
 839class QuadraticTerm(QuadraticBase):
 840    """The product of a scalar and two variables.
 841
 842    This class is immutable.
 843    """
 844
 845    __slots__ = "_key", "_coefficient"
 846
 847    def __init__(self, key: QuadraticTermKey, coefficient: float) -> None:
 848        self._key: QuadraticTermKey = key
 849        self._coefficient: float = coefficient
 850
 851    @property
 852    def key(self) -> QuadraticTermKey:
 853        return self._key
 854
 855    @property
 856    def coefficient(self) -> float:
 857        return self._coefficient
 858
 859    def _quadratic_flatten_once_and_add_to(
 860        self,
 861        scale: float,
 862        processed_elements: _QuadraticProcessedElements,
 863        target_stack: _ToProcessElements,
 864    ) -> None:
 865        processed_elements.quadratic_terms[self._key] += self._coefficient * scale
 866
 867    def __mul__(self, constant: float) -> "QuadraticTerm":
 868        if not isinstance(constant, (int, float)):
 869            return NotImplemented
 870        return QuadraticTerm(self._key, self._coefficient * constant)
 871
 872    def __rmul__(self, constant: float) -> "QuadraticTerm":
 873        if not isinstance(constant, (int, float)):
 874            return NotImplemented
 875        return QuadraticTerm(self._key, self._coefficient * constant)
 876
 877    def __truediv__(self, constant: float) -> "QuadraticTerm":
 878        if not isinstance(constant, (int, float)):
 879            return NotImplemented
 880        return QuadraticTerm(self._key, self._coefficient / constant)
 881
 882    def __neg__(self) -> "QuadraticTerm":
 883        return QuadraticTerm(self._key, -self._coefficient)
 884
 885    def __str__(self):
 886        return f"{self._coefficient} * {self._key!s}"
 887
 888    def __repr__(self):
 889        return f"QuadraticTerm({self._key!r}, {self._coefficient})"
 890
 891
 892class LinearExpression(LinearBase):
 893    """For variables x, an expression: b + sum_{i in I} a_i * x_i.
 894
 895    This class is immutable.
 896    """
 897
 898    __slots__ = "__weakref__", "_terms", "_offset"
 899
 900    # TODO(b/216492143): consider initializing from a dictionary.
 901    def __init__(self, /, other: LinearTypes = 0) -> None:
 902        self._offset: float = 0.0
 903        if isinstance(other, (int, float)):
 904            self._offset = float(other)
 905            self._terms: Mapping[Variable, float] = immutabledict.immutabledict()
 906            return
 907
 908        to_process: _LinearToProcessElements = _LinearToProcessElements(other, 1.0)
 909        processed_elements = _ProcessedElements()
 910        while to_process:
 911            linear, coef = to_process.pop()
 912            linear._flatten_once_and_add_to(coef, processed_elements, to_process)
 913        # TODO(b/216492143): explore avoiding this copy.
 914        self._terms: Mapping[Variable, float] = immutabledict.immutabledict(
 915            processed_elements.terms
 916        )
 917        self._offset = processed_elements.offset
 918
 919    @property
 920    def terms(self) -> Mapping[Variable, float]:
 921        return self._terms
 922
 923    @property
 924    def offset(self) -> float:
 925        return self._offset
 926
 927    def evaluate(self, variable_values: Mapping[Variable, float]) -> float:
 928        """Returns the value of this expression for given variable values.
 929
 930        E.g. if this is 3 * x + 4 and variable_values = {x: 2.0}, then
 931        evaluate(variable_values) equals 10.0.
 932
 933        See also mathopt.evaluate_expression(), which works on any type in
 934        QuadraticTypes.
 935
 936        Args:
 937          variable_values: Must contain a value for every variable in expression.
 938
 939        Returns:
 940          The value of this expression when replacing variables by their value.
 941        """
 942        result = self._offset
 943        for var, coef in sorted(
 944            self._terms.items(), key=lambda var_coef_pair: var_coef_pair[0].id
 945        ):
 946            result += coef * variable_values[var]
 947        return result
 948
 949    def _flatten_once_and_add_to(
 950        self,
 951        scale: float,
 952        processed_elements: _ProcessedElements,
 953        target_stack: _ToProcessElements,
 954    ) -> None:
 955        for var, val in self._terms.items():
 956            processed_elements.terms[var] += val * scale
 957        processed_elements.offset += scale * self.offset
 958
 959    # TODO(b/216492143): change __str__ to match C++ implementation in
 960    # cl/421649402.
 961    def __str__(self):
 962        """Returns the name, or a string containing the id if the name is empty."""
 963        result = str(self.offset)
 964        sorted_keys = sorted(self._terms.keys(), key=str)
 965        for var in sorted_keys:
 966            # TODO(b/216492143): consider how to better deal with `NaN` and try to
 967            # match C++ implementation in cl/421649402. See TODO for StrAndReprTest in
 968            # linear_expression_test.py.
 969            coefficient = self._terms[var]
 970            if coefficient == 0.0:
 971                continue
 972            if coefficient > 0:
 973                result += " + "
 974            else:
 975                result += " - "
 976            result += str(abs(coefficient)) + " * " + str(var)
 977        return result
 978
 979    def __repr__(self):
 980        result = f"LinearExpression({self.offset}, " + "{"
 981        result += ", ".join(
 982            f"{var!r}: {coefficient}" for var, coefficient in self._terms.items()
 983        )
 984        result += "})"
 985        return result
 986
 987
 988class QuadraticExpression(QuadraticBase):
 989    """For variables x, an expression: b + sum_{i in I} a_i * x_i + sum_{i,j in I, i<=j} a_i,j * x_i * x_j.
 990
 991    This class is immutable.
 992    """
 993
 994    __slots__ = "__weakref__", "_linear_terms", "_quadratic_terms", "_offset"
 995
 996    # TODO(b/216492143): consider initializing from a dictionary.
 997    def __init__(self, other: QuadraticTypes) -> None:
 998        self._offset: float = 0.0
 999        if isinstance(other, (int, float)):
1000            self._offset = float(other)
1001            self._linear_terms: Mapping[Variable, float] = immutabledict.immutabledict()
1002            self._quadratic_terms: Mapping[QuadraticTermKey, float] = (
1003                immutabledict.immutabledict()
1004            )
1005            return
1006
1007        to_process: _QuadraticToProcessElements = _QuadraticToProcessElements(
1008            other, 1.0
1009        )
1010        processed_elements = _QuadraticProcessedElements()
1011        while to_process:
1012            linear_or_quadratic, coef = to_process.pop()
1013            if isinstance(linear_or_quadratic, LinearBase):
1014                linear_or_quadratic._flatten_once_and_add_to(
1015                    coef, processed_elements, to_process
1016                )
1017            else:
1018                linear_or_quadratic._quadratic_flatten_once_and_add_to(
1019                    coef, processed_elements, to_process
1020                )
1021        # TODO(b/216492143): explore avoiding this copy.
1022        self._linear_terms: Mapping[Variable, float] = immutabledict.immutabledict(
1023            processed_elements.terms
1024        )
1025        self._quadratic_terms: Mapping[QuadraticTermKey, float] = (
1026            immutabledict.immutabledict(processed_elements.quadratic_terms)
1027        )
1028        self._offset = processed_elements.offset
1029
1030    @property
1031    def linear_terms(self) -> Mapping[Variable, float]:
1032        return self._linear_terms
1033
1034    @property
1035    def quadratic_terms(self) -> Mapping[QuadraticTermKey, float]:
1036        return self._quadratic_terms
1037
1038    @property
1039    def offset(self) -> float:
1040        return self._offset
1041
1042    def evaluate(self, variable_values: Mapping[Variable, float]) -> float:
1043        """Returns the value of this expression for given variable values.
1044
1045        E.g. if this is 3 * x * x + 4 and variable_values = {x: 2.0}, then
1046        evaluate(variable_values) equals 16.0.
1047
1048        See also mathopt.evaluate_expression(), which works on any type in
1049        QuadraticTypes.
1050
1051        Args:
1052          variable_values: Must contain a value for every variable in expression.
1053
1054        Returns:
1055          The value of this expression when replacing variables by their value.
1056        """
1057        result = self._offset
1058        for var, coef in sorted(
1059            self._linear_terms.items(),
1060            key=lambda var_coef_pair: var_coef_pair[0].id,
1061        ):
1062            result += coef * variable_values[var]
1063        for key, coef in sorted(
1064            self._quadratic_terms.items(),
1065            key=lambda quad_coef_pair: (
1066                quad_coef_pair[0].first_var.id,
1067                quad_coef_pair[0].second_var.id,
1068            ),
1069        ):
1070            result += (
1071                coef * variable_values[key.first_var] * variable_values[key.second_var]
1072            )
1073        return result
1074
1075    def _quadratic_flatten_once_and_add_to(
1076        self,
1077        scale: float,
1078        processed_elements: _QuadraticProcessedElements,
1079        target_stack: _QuadraticToProcessElements,
1080    ) -> None:
1081        for var, val in self._linear_terms.items():
1082            processed_elements.terms[var] += val * scale
1083        for key, val in self._quadratic_terms.items():
1084            processed_elements.quadratic_terms[key] += val * scale
1085        processed_elements.offset += scale * self.offset
1086
1087    # TODO(b/216492143): change __str__ to match C++ implementation in
1088    # cl/421649402.
1089    def __str__(self):
1090        result = str(self.offset)
1091        sorted_linear_keys = sorted(self._linear_terms.keys(), key=str)
1092        for var in sorted_linear_keys:
1093            # TODO(b/216492143): consider how to better deal with `NaN` and try to
1094            # match C++ implementation in cl/421649402. See TODO for StrAndReprTest in
1095            # linear_expression_test.py.
1096            coefficient = self._linear_terms[var]
1097            if coefficient == 0.0:
1098                continue
1099            if coefficient > 0:
1100                result += " + "
1101            else:
1102                result += " - "
1103            result += str(abs(coefficient)) + " * " + str(var)
1104        sorted_quadratic_keys = sorted(self._quadratic_terms.keys(), key=str)
1105        for key in sorted_quadratic_keys:
1106            # TODO(b/216492143): consider how to better deal with `NaN` and try to
1107            # match C++ implementation in cl/421649402. See TODO for StrAndReprTest in
1108            # linear_expression_test.py.
1109            coefficient = self._quadratic_terms[key]
1110            if coefficient == 0.0:
1111                continue
1112            if coefficient > 0:
1113                result += " + "
1114            else:
1115                result += " - "
1116            result += str(abs(coefficient)) + " * " + str(key)
1117        return result
1118
1119    def __repr__(self):
1120        result = f"QuadraticExpression({self.offset}, " + "{"
1121        result += ", ".join(
1122            f"{var!r}: {coefficient}" for var, coefficient in self._linear_terms.items()
1123        )
1124        result += "}, {"
1125        result += ", ".join(
1126            f"{key!r}: {coefficient}"
1127            for key, coefficient in self._quadratic_terms.items()
1128        )
1129        result += "})"
1130        return result
1131
1132
1133class LinearSum(LinearBase):
1134    # TODO(b/216492143): consider what details to move elsewhere and/or replace
1135    # by examples, and do complexity analysis.
1136    """A deferred sum of LinearBase objects.
1137
1138    LinearSum objects are automatically created when two linear objects are added
1139    and, as noted in the documentation for Linear, can reduce the inefficiencies.
1140    In particular, they are created when calling sum(iterable) when iterable is
1141    an Iterable[LinearTypes]. However, using LinearSum(iterable) instead
1142    can result in additional performance improvements:
1143
1144      * sum(iterable): creates a nested set of LinearSum objects (e.g.
1145        `sum([a, b, c])` is `LinearSum(0, LinearSum(a, LinearSum(b, c)))`).
1146      * LinearSum(iterable): creates a single LinearSum that saves a tuple with
1147        all the LinearTypes objects in iterable (e.g.
1148        `LinearSum([a, b, c])` does not create additional objects).
1149
1150    This class is immutable.
1151    """
1152
1153    __slots__ = "__weakref__", "_elements"
1154
1155    # Potentially unsafe use of Iterable argument is handled by immediate local
1156    # storage as tuple.
1157    def __init__(self, iterable: Iterable[LinearTypes]) -> None:
1158        """Creates a LinearSum object. A copy of iterable is saved as a tuple."""
1159
1160        self._elements = tuple(iterable)
1161        for item in self._elements:
1162            if not isinstance(item, (LinearBase, int, float)):
1163                raise TypeError(
1164                    "unsupported type in iterable argument for "
1165                    f"LinearSum: {type(item).__name__!r}"
1166                )
1167
1168    @property
1169    def elements(self) -> Tuple[LinearTypes, ...]:
1170        return self._elements
1171
1172    def _flatten_once_and_add_to(
1173        self,
1174        scale: float,
1175        processed_elements: _ProcessedElements,
1176        target_stack: _ToProcessElements,
1177    ) -> None:
1178        for term in self._elements:
1179            if isinstance(term, (int, float)):
1180                processed_elements.offset += scale * float(term)
1181            else:
1182                target_stack.append(term, scale)
1183
1184    def __str__(self):
1185        return str(as_flat_linear_expression(self))
1186
1187    def __repr__(self):
1188        result = "LinearSum(("
1189        result += ", ".join(repr(linear) for linear in self._elements)
1190        result += "))"
1191        return result
1192
1193
1194class QuadraticSum(QuadraticBase):
1195    # TODO(b/216492143): consider what details to move elsewhere and/or replace
1196    # by examples, and do complexity analysis.
1197    """A deferred sum of QuadraticTypes objects.
1198
1199    QuadraticSum objects are automatically created when a quadratic object is
1200    added to quadratic or linear objects and, as has performance optimizations
1201    similar to LinearSum.
1202
1203    This class is immutable.
1204    """
1205
1206    __slots__ = "__weakref__", "_elements"
1207
1208    # Potentially unsafe use of Iterable argument is handled by immediate local
1209    # storage as tuple.
1210    def __init__(self, iterable: Iterable[QuadraticTypes]) -> None:
1211        """Creates a QuadraticSum object. A copy of iterable is saved as a tuple."""
1212
1213        self._elements = tuple(iterable)
1214        for item in self._elements:
1215            if not isinstance(item, (LinearBase, QuadraticBase, int, float)):
1216                raise TypeError(
1217                    "unsupported type in iterable argument for "
1218                    f"QuadraticSum: {type(item).__name__!r}"
1219                )
1220
1221    @property
1222    def elements(self) -> Tuple[QuadraticTypes, ...]:
1223        return self._elements
1224
1225    def _quadratic_flatten_once_and_add_to(
1226        self,
1227        scale: float,
1228        processed_elements: _QuadraticProcessedElements,
1229        target_stack: _QuadraticToProcessElements,
1230    ) -> None:
1231        for term in self._elements:
1232            if isinstance(term, (int, float)):
1233                processed_elements.offset += scale * float(term)
1234            else:
1235                target_stack.append(term, scale)
1236
1237    def __str__(self):
1238        return str(as_flat_quadratic_expression(self))
1239
1240    def __repr__(self):
1241        result = "QuadraticSum(("
1242        result += ", ".join(repr(element) for element in self._elements)
1243        result += "))"
1244        return result
1245
1246
1247class LinearProduct(LinearBase):
1248    """A deferred multiplication computation for linear expressions.
1249
1250    This class is immutable.
1251    """
1252
1253    __slots__ = "_scalar", "_linear"
1254
1255    def __init__(self, scalar: float, linear: LinearBase) -> None:
1256        if not isinstance(scalar, (float, int)):
1257            raise TypeError(
1258                "unsupported type for scalar argument in "
1259                f"LinearProduct: {type(scalar).__name__!r}"
1260            )
1261        if not isinstance(linear, LinearBase):
1262            raise TypeError(
1263                "unsupported type for linear argument in "
1264                f"LinearProduct: {type(linear).__name__!r}"
1265            )
1266        self._scalar: float = float(scalar)
1267        self._linear: LinearBase = linear
1268
1269    @property
1270    def scalar(self) -> float:
1271        return self._scalar
1272
1273    @property
1274    def linear(self) -> LinearBase:
1275        return self._linear
1276
1277    def _flatten_once_and_add_to(
1278        self,
1279        scale: float,
1280        processed_elements: _ProcessedElements,
1281        target_stack: _ToProcessElements,
1282    ) -> None:
1283        target_stack.append(self._linear, self._scalar * scale)
1284
1285    def __str__(self):
1286        return str(as_flat_linear_expression(self))
1287
1288    def __repr__(self):
1289        result = f"LinearProduct({self._scalar!r}, "
1290        result += f"{self._linear!r})"
1291        return result
1292
1293
1294class QuadraticProduct(QuadraticBase):
1295    """A deferred multiplication computation for quadratic expressions.
1296
1297    This class is immutable.
1298    """
1299
1300    __slots__ = "_scalar", "_quadratic"
1301
1302    def __init__(self, scalar: float, quadratic: QuadraticBase) -> None:
1303        if not isinstance(scalar, (float, int)):
1304            raise TypeError(
1305                "unsupported type for scalar argument in "
1306                f"QuadraticProduct: {type(scalar).__name__!r}"
1307            )
1308        if not isinstance(quadratic, QuadraticBase):
1309            raise TypeError(
1310                "unsupported type for linear argument in "
1311                f"QuadraticProduct: {type(quadratic).__name__!r}"
1312            )
1313        self._scalar: float = float(scalar)
1314        self._quadratic: QuadraticBase = quadratic
1315
1316    @property
1317    def scalar(self) -> float:
1318        return self._scalar
1319
1320    @property
1321    def quadratic(self) -> QuadraticBase:
1322        return self._quadratic
1323
1324    def _quadratic_flatten_once_and_add_to(
1325        self,
1326        scale: float,
1327        processed_elements: _QuadraticProcessedElements,
1328        target_stack: _QuadraticToProcessElements,
1329    ) -> None:
1330        target_stack.append(self._quadratic, self._scalar * scale)
1331
1332    def __str__(self):
1333        return str(as_flat_quadratic_expression(self))
1334
1335    def __repr__(self):
1336        return f"QuadraticProduct({self._scalar}, {self._quadratic!r})"
1337
1338
1339class LinearLinearProduct(QuadraticBase):
1340    """A deferred multiplication of two linear expressions.
1341
1342    This class is immutable.
1343    """
1344
1345    __slots__ = "_first_linear", "_second_linear"
1346
1347    def __init__(self, first_linear: LinearBase, second_linear: LinearBase) -> None:
1348        if not isinstance(first_linear, LinearBase):
1349            raise TypeError(
1350                "unsupported type for first_linear argument in "
1351                f"LinearLinearProduct: {type(first_linear).__name__!r}"
1352            )
1353        if not isinstance(second_linear, LinearBase):
1354            raise TypeError(
1355                "unsupported type for second_linear argument in "
1356                f"LinearLinearProduct: {type(second_linear).__name__!r}"
1357            )
1358        self._first_linear: LinearBase = first_linear
1359        self._second_linear: LinearBase = second_linear
1360
1361    @property
1362    def first_linear(self) -> LinearBase:
1363        return self._first_linear
1364
1365    @property
1366    def second_linear(self) -> LinearBase:
1367        return self._second_linear
1368
1369    def _quadratic_flatten_once_and_add_to(
1370        self,
1371        scale: float,
1372        processed_elements: _QuadraticProcessedElements,
1373        target_stack: _QuadraticToProcessElements,
1374    ) -> None:
1375        # A recursion is avoided here because as_flat_linear_expression() must never
1376        # call _quadratic_flatten_once_and_add_to().
1377        first_expression = as_flat_linear_expression(self._first_linear)
1378        second_expression = as_flat_linear_expression(self._second_linear)
1379        processed_elements.offset += (
1380            first_expression.offset * second_expression.offset * scale
1381        )
1382        for first_var, first_val in first_expression.terms.items():
1383            processed_elements.terms[first_var] += (
1384                second_expression.offset * first_val * scale
1385            )
1386        for second_var, second_val in second_expression.terms.items():
1387            processed_elements.terms[second_var] += (
1388                first_expression.offset * second_val * scale
1389            )
1390
1391        for first_var, first_val in first_expression.terms.items():
1392            for second_var, second_val in second_expression.terms.items():
1393                processed_elements.quadratic_terms[
1394                    QuadraticTermKey(first_var, second_var)
1395                ] += (first_val * second_val * scale)
1396
1397    def __str__(self):
1398        return str(as_flat_quadratic_expression(self))
1399
1400    def __repr__(self):
1401        result = "LinearLinearProduct("
1402        result += f"{self._first_linear!r}, "
1403        result += f"{self._second_linear!r})"
1404        return result
1405
1406
1407def as_flat_linear_expression(value: LinearTypes) -> LinearExpression:
1408    """Converts floats, ints and Linear objects to a LinearExpression."""
1409    if isinstance(value, LinearExpression):
1410        return value
1411    return LinearExpression(value)
1412
1413
1414def as_flat_quadratic_expression(value: QuadraticTypes) -> QuadraticExpression:
1415    """Converts floats, ints, LinearBase and QuadraticBase objects to a QuadraticExpression."""
1416    if isinstance(value, QuadraticExpression):
1417        return value
1418    return QuadraticExpression(value)