ortools.math_opt.python.variables

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