Linear expressions¶

Linear expressions are linear combinations of iterates and function values, with arithmetic and @ support, used to state objectives and performance measures.

LinearExpression ¶

A linear combination of function values, inner products (between points and/ or gradients) and constant scalars.

Attributes:

ndim : int
    The dimension of underlying space, i.e., the size of each coefficient matrix.

is_leaf : bool
    Indicates whether this expression is a primitive ("leaf") function value (i.e. not
    itself built from other `LinearExpression` objects). If `is_leaf` is True, this
    object is a function value defined from scratch.

is_binary : bool
    Indicates whether a leaf expression is intended to be binary or not (i.e. constrained to only have values 0 or 1 in each dimension).

decomposition_dict : dict
    A mapping from each leaf expression to its corresponding coefficient matrix. If
    `is_leaf` is True, this dict maps the object to its own coefficient matrix.

counter : int
    Tracks the number of leaf `LinearExpression` objects.

References

.. S. Diamond and S. Boyd. "CVXPY: A Python-Embedded Modeling Language for Convex
   Optimization." Journal of Machine Learning Research, 17(83):1-5, 2016.
.. B. Goujaud, C. Moucer, F. Glineur, J. Hendrickx, A. Taylor, A. Dieuleveut (2022).
   "PEPit: computer-assisted worst-case analyses of first-order optimization methods
   in Python."

Source code in fomtools/linearexpression.py

class LinearExpression:
    """
    A linear combination of function values, inner products (between points and/ or gradients)
    and constant scalars.

    Attributes:
    ----------
        ndim : int
            The dimension of underlying space, i.e., the size of each coefficient matrix.

        is_leaf : bool
            Indicates whether this expression is a primitive ("leaf") function value (i.e. not
            itself built from other `LinearExpression` objects). If `is_leaf` is True, this
            object is a function value defined from scratch.

        is_binary : bool
            Indicates whether a leaf expression is intended to be binary or not (i.e. constrained to only have values 0 or 1 in each dimension).

        decomposition_dict : dict
            A mapping from each leaf expression to its corresponding coefficient matrix. If
            `is_leaf` is True, this dict maps the object to its own coefficient matrix.

        counter : int
            Tracks the number of leaf `LinearExpression` objects.

    References
    ----------
        .. S. Diamond and S. Boyd. "CVXPY: A Python-Embedded Modeling Language for Convex
           Optimization." Journal of Machine Learning Research, 17(83):1-5, 2016.
        .. B. Goujaud, C. Moucer, F. Glineur, J. Hendrickx, A. Taylor, A. Dieuleveut (2022).
           "PEPit: computer-assisted worst-case analyses of first-order optimization methods
           in Python."

    """

    counter = 0
    # this is necessary else numpy will not even look at the @ operator due to precedence
    __array_priority__ = 1000
    # The Verifier a leaf is registered with; set by ``Verifier._register_var``.
    _verifier = None
    # ``(a, b)`` when this expression was built as ``a - b``; lets the Verifier
    # recognize a successive-residual objective (see ``Verifier.maximize``).
    _difference = None

    def __init__(self, decomposition_dict: dict, const: np.ndarray = None, is_binary: bool = False):
        """
        Initialize a `LinearExpression` object with decomposition dictionary.

        Parameters
        ----------
        decomposition_dict : dict
            A mapping from each leaf `LinearExpression` to its coefficient matrix (an nxn sparse
            matrix).

        const : ndarray or None, optional
            A one-dimensional array or None (default). If `const` is None, the `const` attribute
            of this object will be set to a `numpy.ndarray` of length `shape` filled with zeros.

        is_binary : bool, optional
            A flag to determine if a leaf element is intended to be binary (0 or 1 in each dimension) or not. Defaults to `False`.

        Raises
        ------
        ValueError
            If all the coefficient matrices in the `decomposition_dict` doesn't have the same number
            of rows.

        ValueError
            If `const` is not one-dimensional.

        ValueError
            If the number of rows in `const` does not equal the number of rows in coefficient
            matrices in the `decomposition_dict`.
        """

        for leaf, mat in decomposition_dict.items():
            if not isinstance(leaf, LinearExpression) or not leaf.is_leaf:
                raise ValueError("Decomposition keys must be leaf expressions.")
            if len(mat.shape) != 2 or mat.shape[1] != leaf.ndim:
                raise ValueError(
                    "Each coefficient must be a matrix with one column per leaf entry."
                )
        shapes = {mat.shape[0] for mat in decomposition_dict.values()}
        if len(shapes) > 1:
            raise ValueError(
                f"All coefficient matrices must have the same number of rows: {shapes}"
            )
        self.ndim = next(iter(shapes), 0)
        if const is not None:
            const = np.asarray(const, dtype=float)
            if const.ndim != 1:
                raise ValueError("The constant must be a one-dimensional vector.")
            if not shapes:
                self.ndim = const.size
            if const.shape != (self.ndim,):
                raise ValueError("The constant must have one entry per coefficient row.")
        self.const = np.zeros(self.ndim) if const is None else const
        self.decomposition_dict = decomposition_dict
        self.counter = LinearExpression.counter
        LinearExpression.counter += 1
        self.is_leaf = False
        self.is_binary = is_binary
        self.branch_priority = 0
        self.lb = [i.lb for i in decomposition_dict.keys()]
        self.ub = [i.ub for i in decomposition_dict.keys()]

    @classmethod
    def from_int(
        cls,
        ndim: int,
        is_binary: bool = False,
        lb: float = -np.inf,
        ub: float = np.inf,
        branch_priority: int = 0,
    ) -> Self:
        """
        Initialize a `LinearExpression` object with an integer `shape`. Internally, this
        creates a decomposition dictionary that maps the `LinearExpression` object with a sparse
        identity matrix of shape `(shape, shape)`.

        Parameters
        ----------
        ndim : int
            The dimension of underlying space, i.e., the size of each coefficient matrix.
        is_binary: bool
            Flag to determine if the leaf expression is binary or not (0 or 1 in each dimension).
        branch_priority: int, default 0
            Branching priority hint for a binary leaf: branch-and-bound solvers that
            support priorities branch on higher values first. Solvers without such
            a notion ignore it.

        Returns
        -------
        LinearExpression
            A new `LinearExpression` instance whose decomposition contains a single
            entry: the instance itself as a key, and a SciPy sparse identity matrix of
            shape `(shape, shape)` as the value.
        """
        _reject_nan_bounds(lb, ub)
        obj = cls.__new__(cls)  # uninitialized instance
        obj.is_leaf = True
        obj.decomposition_dict = {obj: spa.eye(ndim)}
        obj.ndim = ndim
        obj.counter = cls.counter
        obj.const = np.zeros(ndim)
        obj.is_binary = is_binary
        obj.branch_priority = branch_priority
        obj.lb = np.zeros(ndim) if is_binary else np.full(ndim, lb, dtype=float)
        obj.ub = np.ones(ndim) if is_binary else np.full(ndim, ub, dtype=float)
        cls.counter += 1
        return obj

    def __getstate__(self):
        # The Verifier back-reference is not part of the expression: copies and
        # pickles would otherwise drag in the whole Verifier and its solver models.
        state = self.__dict__.copy()
        state.pop("_verifier", None)
        return state

    def __str__(self):
        return f"Var{self.counter}"

    def __repr__(self):
        return f"<LinearExpression {'Leaf' if self.is_leaf else ''}, dim={self.ndim}>"

    def __hash__(self):
        """
        Return a hash based on this expression's unique counter.

        Each LinearExpression is assigned a unique, monotonically increasing
        counter at construction. We use a tuple hash to avoid collisions with
        integers, which is necessary because __eq__ returns an EqualityConstraint
        (truthy) rather than a bool. Without this, dict[0] could incorrectly
        match a LinearExpression with counter=0.
        """
        return hash(("LinearExpression", self.counter))

    def __getitem__(self, item: Self | int):
        """
        Retrieve a coefficient matrix or a sliced LinearExpression corresponding
        to `item`.

        If the `item` is a leaf expression, this method returns its corresponding
        coefficient matrix. If the `item` is an `int` or a `slice`, this method
        returns a new `LinearExpression` instance representing a specified subset of
        rows from all the corresponding coefficients in the decomposition dictionary.

        Raises
        ------
        KeyError
            If the specified leaf expression is not found in this `LinearExpression` object.
        """
        try:
            return self.decomposition_dict[item]
        except KeyError:
            try:
                return LinearExpression(
                    decomposition_dict={
                        k: v.tocsr()[item] if spa.issparse(v) else np.atleast_2d(v[item])
                        for k, v in self.decomposition_dict.items()
                    },
                    const=np.atleast_1d(self.const[item]),
                )
            except TypeError:
                raise KeyError("""
                The specified leaf expression is not present in this LinearExpression object.
                """)

    def __add__(self, other: Union[Self, np.array, list, int, float]) -> Self:
        """
        Add two `LinearExpression` objects, ensuring they have the same dimension.

        Parameters
        ----------
        other : LinearExpression, np.array, list, int, float
            The expression or a vector to add to this one.

        Returns
        -------
        LinearExpression
            A new `LinearExpression` object whose decomposition maps each leaf in the union of both
            expressiom to the sum of its coefficient matrices, treating any leaf missing from one
            operand as having a zero coefficient matrix.

        Raises:
        ------
        ValueError
            If the objects (`LinearExpression` or a vector) to be added together does not have
            the same dimension.

        ValueError
            If the object to be added is not of one of the following types: `LinearExpression`,
            `np.ndarray`,  `float`, `int`, or `list`.
        """
        try:
            return LinearExpression(
                decomposition_dict=self.decomposition_dict,
                const=self.const + np.array(other).astype(float),
            )
        except ValueError:
            try:
                # Check to see if other is of type list or a numpy array
                if len(other) == self.ndim:
                    return LinearExpression(
                        decomposition_dict=self.decomposition_dict, const=self.const + other
                    )
                else:
                    raise ValueError(
                        f"Cannot add constant of mismatched dimensions. Expected dimension: {self.ndim}, got {len(other)}"
                    )
            except TypeError:
                try:
                    # Check to see if other is of type LinearExpression
                    if self.ndim == other.ndim:
                        merged_decomposition_dict = merge_dict(
                            self.decomposition_dict, other.decomposition_dict
                        )
                        return LinearExpression(
                            decomposition_dict=prune_dict(merged_decomposition_dict),
                            const=self.const + other.const,
                        )
                    else:
                        raise ValueError(
                            f"Cannot add LinearExpression objects of mismatched dimensions. Expected dimension: {self.ndim}, got {other.ndim}"
                        )
                except AttributeError:
                    raise ValueError(
                        f"Can only add LinearExpression objects to a LinearExpression object, numpy arrays, list, float, or an int got type {type(other)}."
                    )

    def __radd__(self, other: Union[Self, np.array, list]) -> Self:
        """
        Reflected addition to support other + expression.

        This method is invoked when a `LinearExpression` object appears on
        the right-hand side of a `+` operation (e.g. `np.array([1,2,3]) + expr`).
        It delegates to `__add__`, so that both `np.array([1,2,3]) + expr` and
        `expr + np.array([1,2,3])` behave identically.

        Parameters
        ----------
        other : LinearExpression, np.array, list
            The expression or a vector to add to this one.

        Returns
        -------
        LinearExpression
            A new `LinearExpression` object whose decomposition maps each leaf in the union of both
            expressiom to the sum of its coefficient matrices, treating any leaf missing from one
            operand as having a zero coefficient matrix.

        Raises:
        ------
        ValueError
            If the objects (`LinearExpression` or a vector) to be added together does not have
            the same dimension.

        ValueError
            If the object to be added is not of one of the following types: `LinearExpression`,
            `np.ndarray`, or `list`.
        """
        return self + other

    def __mul__(self, scalar: Union[float, int]) -> Self:
        """
        Multiply this `LinearExpression` object by a scalar.

        Parameters
        ----------
        scalar : float or int
            The numeric factor to multiply each coefficient matrix by.

        Returns
        -------
        LinearExpression
            A new `LinearExpression` object in which each leaf’s coefficient matrix is multiplied
            by the given `scalar`.

        Raises:
        ------
        TypeError
            If the `scalar` is not an instance of int or float.

        """
        factor = np.asarray(scalar)
        if factor.ndim != 0 or not np.issubdtype(factor.dtype, np.number):
            raise TypeError(
                "LinearExpression multiplication requires a scalar; use a matrix @ expression for vector scaling."
            )
        factor = float(factor)
        return LinearExpression(
            {leaf: coeff * factor for leaf, coeff in self.decomposition_dict.items()},
            const=self.const * factor,
        )

    def __rmul__(self, scalar: Union[float, int]) -> Self:
        """
        Reflected multiplication to support scalar * expression.

        This method is invoked when a `LinearExpression` object appears on the
        right-hand side of a `*` operation (e.g. `3 * expr`). It delegates to
        to `__mul__`, so that both `expr * 3` and `3  * expr` behave identically.

        Parameters
        ----------
        scalar : float or int
            The numeric factor to multiply each coefficient matrix by.

        Returns
        -------
        LinearExpression
            A new `LinearExpression` in which each leaf’s coefficient matrix is multiplied
            by the given `scalar`.

        Raises:
        ------
        TypeError
            If the `scalar` is not an instance of int or float.
        """
        return self * scalar

    def __truediv__(self, scalar: Union[float, int]) -> Self:
        """
        Divide this LinearExpression by a scalar factor.

        This method is invoked when the expression appears on the left-hand side
        of a true division (e.g. `expr / 3`).

        Parameters
        ----------
        scalar : float or int
            The numeric divisor to apply to every coefficient matrix.

        Returns
        -------
        LinearExpression
            A new `LinearExpression` in which each leaf's coefficient matrix is divided
            by the given `scalar`.

        Raises
        ------
        TypeError
            If the `scalar` is not an instance of int or float.

        ZeroDivisionError
            If `scalar` is zero.
        """
        if scalar == 0:
            raise ZeroDivisionError("Division of LinearExpression by zero is not allowed.")

        return self * (1 / scalar)

    def __neg__(self) -> Self:
        """
        Compute the negation of this LinearExpression.

        This method is invoked for unary negation (e.g., `-expr`). It returns a new
        expression with each coefficient matrix in the decomposition multiplied by -1.

        Returns
        -------
        LinearExpression
            A new `LinearExpression` object with all coefficient matrices negated.
        """
        return self * -1

    def __sub__(self, other: Self) -> Self:
        """
        Subtract one LinearExpression from another.

        Parameters
        ----------
        other : LinearExpression, np.array, list
            The expression or a vector xto subtract from this one.

        Returns
        -------
        LinearExpression
            A new `LinearExpression` object whose decomposition maps each leaf in the union of
            both expression to the difference of its coefficient matrices, treating any leaf
            missing from one operand as having a zero coefficient matrix.

        Raises
        ------
        ValueError
            If the two `LinearExpression` instances have mismatched dimensions.

        ValueError
            If the object to be subtracted is not of one of the following types: `LinearExpression`,
            `np.ndarray`, or `list`.

        """
        result = self + (-other)
        if isinstance(other, LinearExpression):
            result._difference = (self, other)
        return result

    def __rsub__(self, other: Self) -> Self:
        """
        Reflected subtraction to support other - expression.

        This method is invoked when a `LinearExpression` object appears on
        the right-hand side of a `-` operation (e.g. `np.array([1,2,3]) - expr`).

        Parameters
        ----------
        other : LinearExpression, np.array, list
            The expression or a vector that this one is to be subtracted from.

        Returns
        -------
        LinearExpression
            A new `LinearExpression` object whose decomposition maps each leaf in the union of
            both expression to the difference of its coefficient matrices, treating any leaf
            missing from one operand as having a zero coefficient matrix.

        Raises
        ------
        ValueError
            If the two `LinearExpression` instances have mismatched dimensions.

        ValueError
            If the object to be subtracted is not of one of the following types: `LinearExpression`,
            `np.ndarray`, or `list`.

        """
        return (-self) + other

    def __matmul__(self, other):
        # TODO
        raise NotImplementedError("np matrix or sp matrix should be on the left of the @")

    def __rmatmul__(self, matrix: Union[np.ndarray, spa.spmatrix]) -> Self:
        """
        Multiply this `LinearExpression` object by another matrix.

        This method is called when a `LinearExpression` appears on the right‐hand side
        of the `@` operator (e.g., `M @ expr`).

        Parameters
        ----------
        matrix : numpy.ndarray or scipy.sparse.spmatrix
            A matrix of shape `(m, n)`—where `n` is this expression’s dimension—to
            multiply on the left of each coefficient matrix.

        Returns
        -------
        LinearExpression
            A new `LinearExpression` object in which each leaf's coefficient matrix is
            multiplied by the given `matrix`.

        Raises
        ------
        TypeError
            If `other` is not a NumPy array or SciPy sparse matrix.
        ValueError
            If `other.shape[1]` does not match this expression’s dimension `n`.
        """

        if matrix.shape[1] != self.ndim:
            raise ValueError(
                f"""Matrix inner dimension ({matrix.shape[1]}) does not match
                    the LinearExpression dimension ({self.ndim})"""
            )

        try:
            return LinearExpression(
                decomposition_dict={k: matrix @ v for k, v in self.decomposition_dict.items()},
                const=np.asarray(matrix @ self.const).ravel(),
            )
        except TypeError:
            raise TypeError(
                f"""Expected numpy.ndarray or scipy.sparse matrix for multiplication;
                got {type(matrix).__name__}. """
            )

    def __le__(self, rhs: Union[Self, np.ndarray, list]) -> InequalityConstraint:
        """
        Build a less-than-or-equality (`<=`) constraint between this expression and
        another `LinearExpression` object or numpy vector.`

        Parameters
        ----------
        rhs: LinearExpression, np.array, list
            The right-hand side of the inequalit. Scalars are broadcast to the shape of
            `self`. Arrays or expressions must be of same shape with `self`.

        Returns
        -------
        InequalityConstraint
            A constraint object representing `self <= rhs`.

        Raises
        ------
        TypeError
            If `rhs` is not a LinearExpression object, NumPy array or a list.

        ValueError
            If the shapes of `self` and `rhs` are not compatible (i.e., not equal and
            not broadcastable).

        Notes
        -----
        This method does not evaluate the inequality; it only builds a constraint
        for the solver.
        """
        return InequalityConstraint(self, rhs)

    def __eq__(self, rhs: Union[Self, np.ndarray, list]) -> EqualityConstraint:
        """
        Build a equality (`==`) constraint between this expression and
        another `LinearExpression` object or numpy vector.`

        Parameters
        ----------
        rhs: LinearExpression, np.array, list
            The right-hand side of the inequalit. Scalars are broadcast to the shape of
            `self`. Arrays or expressions must be of same shape with `self`.

        Returns
        -------
        EqualityConstraint
            A constraint object representing `self == rhs`.

        Raises
        ------
        TypeError
            If `rhs` is not a LinearExpression object, NumPy array or a list.

        ValueError
            If the shapes of `self` and `rhs` are not compatible (i.e., not equal and
            not broadcastable).

        Notes
        -----
        This method does not evaluate the equality; it only builds a constraint
        for the solver.
        """
        return EqualityConstraint(self, rhs)

    def __ge__(self, rhs: Union[Self, np.ndarray, list]) -> InequalityConstraint:
        """
        Build a greater-than-or-equality (`>=`) constraint between this expression and
        another `LinearExpression` object or numpy vector.`

        Parameters
        ----------
        rhs: LinearExpression, np.array, list
            The right-hand side of the inequality. Scalars are broadcast to the shape of
            `self`. Arrays or expressions must be of same shape with `self`.

        Returns
        -------
        InequalityConstraint
            A constraint object representing `self >= rhs`.

        Raises
        ------
        TypeError
            If `rhs` is not a LinearExpression object, NumPy array or a list.

        ValueError
            If the shapes of `self` and `rhs` are not compatible (i.e., not equal and
            not broadcastable).

        Notes
        -----
        This method does not evaluate the inequality; it only builds a constraint
        for the solver.
        """
        return InequalityConstraint(-self, -rhs)

    def update_bounds(self, lb: np.ndarray, ub: np.ndarray) -> None:
        """Update lower and upper bounds of the `LinearExpression` objects."""
        _reject_nan_bounds(lb, ub)
        self.lb = np.maximum(self.lb, lb)
        self.ub = np.minimum(self.ub, ub)

    def bound_propagation(self) -> tuple[np.ndarray, np.ndarray]:
        """
        Compute the elementwise lower and upper bounds of a linear expression
        given the bound constraints of its coefficient matrices.

        Returns
        -------
        tuple[np.ndarray, np.ndarray]
            A pair (lower, upper) representing the elementwise lower and upper
            bounds of the evaluated expression.

        Raises
        ------
        ValueError
            If any computed lower bound exceeds its corresponding upper bound.
        """

        def _interval_bound_propagation(
            a: np.matrix, lb: np.ndarray, ub: np.ndarray
        ) -> tuple[np.ndarray, np.ndarray]:
            """
            Bounds the linear image y = A @ x for any x with lb ≤ x ≤ ub.

            Using midpoint m = (ub + lb)/2 and radius r = (ub - lb)/2:
                y_min = A @ m - |A| @ r
                y_max = A @ m + |A| @ r

            Returns (y_min, y_max).

            References
            ----------
                .. S. Gowal, K. Dvijotham, R. Stanforth, R. Bunel, C. Qin, J. Uesato, R. Arand-
                   jelovi´c, T. Mann, and Sigma. Kohli. "On the effectiveness of interval bound propa-
                   gation for training verifiably robust models. arXiv:1810.12715, 2018."
            """
            if np.all(np.isfinite(lb)) and np.all(np.isfinite(ub)):
                return (a @ (ub + lb) - np.abs(a) @ (ub - lb)) / 2, (
                    a @ (ub + lb) + np.abs(a) @ (ub - lb)
                ) / 2
            # An infinite bound (e.g. the unbounded output leaf of a linear
            # solve) makes the midpoint inf - inf = NaN, and the NaN then
            # spreads to every later bound. Split A into its positive and
            # negative parts and propagate the finite and infinite parts
            # separately, with the interval convention 0 * inf = 0.
            if spa.issparse(a):
                pos, neg = a.maximum(0), a.minimum(0)
            else:
                pos, neg = np.maximum(a, 0), np.minimum(a, 0)
            lb_f = np.where(np.isfinite(lb), lb, 0.0)
            ub_f = np.where(np.isfinite(ub), ub, 0.0)
            lo = pos @ lb_f + neg @ ub_f
            hi = pos @ ub_f + neg @ lb_f
            to_minus_inf = pos @ np.isneginf(lb).astype(float) - neg @ np.isposinf(ub).astype(float)
            to_plus_inf = pos @ np.isposinf(ub).astype(float) - neg @ np.isneginf(lb).astype(float)
            lo = np.where(np.asarray(to_minus_inf) > 0, -np.inf, lo)
            hi = np.where(np.asarray(to_plus_inf) > 0, np.inf, hi)
            return lo, hi

        out_lb, out_ub = np.zeros(self.ndim), np.zeros(self.ndim)
        for k, v in self.decomposition_dict.items():
            # Check the leaf bounds too: the infinite-bound path would read a NaN as 0.
            _reject_nan_bounds(k.lb, k.ub)
            _lb, _ub = _interval_bound_propagation(v, k.lb, k.ub)

            _reject_nan_bounds(_lb, _ub)
            if np.any(_lb > _ub):
                raise ValueError("Lower bound cannot exceed upper bound .")

            out_lb += _lb
            out_ub += _ub

        # Add constant term to bounds
        out_lb += self.const
        out_ub += self.const

        return out_lb, out_ub

    @property
    def value(self) -> np.ndarray:
        """
        Value of the expression at the worst case found by the last ``solve``.

        For the MIP backend this is the solver's incumbent, a feasible point whose
        objective is a lower bound on the worst case returned by ``solve``.

        Raises
        ------
        RuntimeError
            If the expression is not registered with a ``Verifier``, no incumbent
            is available, or the expression has leaves added after the last solve.
        ValueError
            If the expression mixes leaves of different ``Verifier`` instances.
        NotImplementedError
            With ``method="sdp"`` or ``method="simulator"``, which have no incumbent.
        """
        if not self.decomposition_dict:
            return self.const.copy()
        # Leaves the canonicalizer creates internally (e.g. binaries) have no Verifier.
        verifiers = {
            id(leaf._verifier): leaf._verifier
            for leaf in self.decomposition_dict
            if leaf._verifier is not None
        }
        if not verifiers:
            raise RuntimeError("The expression is not registered with a Verifier.")
        if len(verifiers) > 1:
            raise ValueError("The expression mixes variables of different Verifier instances.")
        return next(iter(verifiers.values()))._solution_value(self)

value `property` ¶

value: ndarray

Value of the expression at the worst case found by the last solve.

For the MIP backend this is the solver's incumbent, a feasible point whose objective is a lower bound on the worst case returned by solve.

Raises:

Type	Description
`RuntimeError`	If the expression is not registered with a `Verifier`, no incumbent is available, or the expression has leaves added after the last solve.
`ValueError`	If the expression mixes leaves of different `Verifier` instances.
`NotImplementedError`	With `method="sdp"` or `method="simulator"`, which have no incumbent.

add ¶

__add__(other: Union[Self, array, list, int, float]) -> Self

Add two LinearExpression objects, ensuring they have the same dimension.

Parameters:

Name	Type	Description	Default
`other`	`(LinearExpression, array, list, int, float)`	The expression or a vector to add to this one.	required

Returns:

Type	Description
`LinearExpression`	A new `LinearExpression` object whose decomposition maps each leaf in the union of both expressiom to the sum of its coefficient matrices, treating any leaf missing from one operand as having a zero coefficient matrix.

Raises:

ValueError If the objects (LinearExpression or a vector) to be added together does not have the same dimension.

ValueError If the object to be added is not of one of the following types: LinearExpression, np.ndarray, float, int, or list.

Source code in fomtools/linearexpression.py

def __add__(self, other: Union[Self, np.array, list, int, float]) -> Self:
    """
    Add two `LinearExpression` objects, ensuring they have the same dimension.

    Parameters
    ----------
    other : LinearExpression, np.array, list, int, float
        The expression or a vector to add to this one.

    Returns
    -------
    LinearExpression
        A new `LinearExpression` object whose decomposition maps each leaf in the union of both
        expressiom to the sum of its coefficient matrices, treating any leaf missing from one
        operand as having a zero coefficient matrix.

    Raises:
    ------
    ValueError
        If the objects (`LinearExpression` or a vector) to be added together does not have
        the same dimension.

    ValueError
        If the object to be added is not of one of the following types: `LinearExpression`,
        `np.ndarray`,  `float`, `int`, or `list`.
    """
    try:
        return LinearExpression(
            decomposition_dict=self.decomposition_dict,
            const=self.const + np.array(other).astype(float),
        )
    except ValueError:
        try:
            # Check to see if other is of type list or a numpy array
            if len(other) == self.ndim:
                return LinearExpression(
                    decomposition_dict=self.decomposition_dict, const=self.const + other
                )
            else:
                raise ValueError(
                    f"Cannot add constant of mismatched dimensions. Expected dimension: {self.ndim}, got {len(other)}"
                )
        except TypeError:
            try:
                # Check to see if other is of type LinearExpression
                if self.ndim == other.ndim:
                    merged_decomposition_dict = merge_dict(
                        self.decomposition_dict, other.decomposition_dict
                    )
                    return LinearExpression(
                        decomposition_dict=prune_dict(merged_decomposition_dict),
                        const=self.const + other.const,
                    )
                else:
                    raise ValueError(
                        f"Cannot add LinearExpression objects of mismatched dimensions. Expected dimension: {self.ndim}, got {other.ndim}"
                    )
            except AttributeError:
                raise ValueError(
                    f"Can only add LinearExpression objects to a LinearExpression object, numpy arrays, list, float, or an int got type {type(other)}."
                )

eq ¶

__eq__(rhs: Union[Self, ndarray, list]) -> EqualityConstraint

Build a equality (==) constraint between this expression and another LinearExpression object or numpy vector.`

Parameters:

Name	Type	Description	Default
`rhs`	`Union[Self, ndarray, list]`	The right-hand side of the inequalit. Scalars are broadcast to the shape of `self`. Arrays or expressions must be of same shape with `self`.	required

Returns:

Type	Description
`EqualityConstraint`	A constraint object representing `self == rhs`.

Raises:

Type	Description
`TypeError`	If `rhs` is not a LinearExpression object, NumPy array or a list.
`ValueError`	If the shapes of `self` and `rhs` are not compatible (i.e., not equal and not broadcastable).

Notes

This method does not evaluate the equality; it only builds a constraint for the solver.

Source code in fomtools/linearexpression.py

def __eq__(self, rhs: Union[Self, np.ndarray, list]) -> EqualityConstraint:
    """
    Build a equality (`==`) constraint between this expression and
    another `LinearExpression` object or numpy vector.`

    Parameters
    ----------
    rhs: LinearExpression, np.array, list
        The right-hand side of the inequalit. Scalars are broadcast to the shape of
        `self`. Arrays or expressions must be of same shape with `self`.

    Returns
    -------
    EqualityConstraint
        A constraint object representing `self == rhs`.

    Raises
    ------
    TypeError
        If `rhs` is not a LinearExpression object, NumPy array or a list.

    ValueError
        If the shapes of `self` and `rhs` are not compatible (i.e., not equal and
        not broadcastable).

    Notes
    -----
    This method does not evaluate the equality; it only builds a constraint
    for the solver.
    """
    return EqualityConstraint(self, rhs)

ge ¶

__ge__(rhs: Union[Self, ndarray, list]) -> InequalityConstraint

Build a greater-than-or-equality (>=) constraint between this expression and another LinearExpression object or numpy vector.`

Parameters:

Name	Type	Description	Default
`rhs`	`Union[Self, ndarray, list]`	The right-hand side of the inequality. Scalars are broadcast to the shape of `self`. Arrays or expressions must be of same shape with `self`.	required

Returns:

Type	Description
`InequalityConstraint`	A constraint object representing `self >= rhs`.

Raises:

Type	Description
`TypeError`	If `rhs` is not a LinearExpression object, NumPy array or a list.
`ValueError`	If the shapes of `self` and `rhs` are not compatible (i.e., not equal and not broadcastable).

Notes

This method does not evaluate the inequality; it only builds a constraint for the solver.

Source code in fomtools/linearexpression.py

def __ge__(self, rhs: Union[Self, np.ndarray, list]) -> InequalityConstraint:
    """
    Build a greater-than-or-equality (`>=`) constraint between this expression and
    another `LinearExpression` object or numpy vector.`

    Parameters
    ----------
    rhs: LinearExpression, np.array, list
        The right-hand side of the inequality. Scalars are broadcast to the shape of
        `self`. Arrays or expressions must be of same shape with `self`.

    Returns
    -------
    InequalityConstraint
        A constraint object representing `self >= rhs`.

    Raises
    ------
    TypeError
        If `rhs` is not a LinearExpression object, NumPy array or a list.

    ValueError
        If the shapes of `self` and `rhs` are not compatible (i.e., not equal and
        not broadcastable).

    Notes
    -----
    This method does not evaluate the inequality; it only builds a constraint
    for the solver.
    """
    return InequalityConstraint(-self, -rhs)

getitem ¶

__getitem__(item: Self | int)

Retrieve a coefficient matrix or a sliced LinearExpression corresponding to item.

If the item is a leaf expression, this method returns its corresponding coefficient matrix. If the item is an int or a slice, this method returns a new LinearExpression instance representing a specified subset of rows from all the corresponding coefficients in the decomposition dictionary.

Raises:

Type	Description
`KeyError`	If the specified leaf expression is not found in this `LinearExpression` object.

Source code in fomtools/linearexpression.py

def __getitem__(self, item: Self | int):
    """
    Retrieve a coefficient matrix or a sliced LinearExpression corresponding
    to `item`.

    If the `item` is a leaf expression, this method returns its corresponding
    coefficient matrix. If the `item` is an `int` or a `slice`, this method
    returns a new `LinearExpression` instance representing a specified subset of
    rows from all the corresponding coefficients in the decomposition dictionary.

    Raises
    ------
    KeyError
        If the specified leaf expression is not found in this `LinearExpression` object.
    """
    try:
        return self.decomposition_dict[item]
    except KeyError:
        try:
            return LinearExpression(
                decomposition_dict={
                    k: v.tocsr()[item] if spa.issparse(v) else np.atleast_2d(v[item])
                    for k, v in self.decomposition_dict.items()
                },
                const=np.atleast_1d(self.const[item]),
            )
        except TypeError:
            raise KeyError("""
            The specified leaf expression is not present in this LinearExpression object.
            """)

hash ¶

__hash__()

Return a hash based on this expression's unique counter.

Each LinearExpression is assigned a unique, monotonically increasing counter at construction. We use a tuple hash to avoid collisions with integers, which is necessary because eq returns an EqualityConstraint (truthy) rather than a bool. Without this, dict[0] could incorrectly match a LinearExpression with counter=0.

Source code in fomtools/linearexpression.py

def __hash__(self):
    """
    Return a hash based on this expression's unique counter.

    Each LinearExpression is assigned a unique, monotonically increasing
    counter at construction. We use a tuple hash to avoid collisions with
    integers, which is necessary because __eq__ returns an EqualityConstraint
    (truthy) rather than a bool. Without this, dict[0] could incorrectly
    match a LinearExpression with counter=0.
    """
    return hash(("LinearExpression", self.counter))

init ¶

__init__(decomposition_dict: dict, const: ndarray = None, is_binary: bool = False)

Parameters:

Name	Type	Description	Default
`decomposition_dict`	`dict`	A mapping from each leaf `LinearExpression` to its coefficient matrix (an nxn sparse matrix).	required
`const`	`ndarray or None`	A one-dimensional array or None (default). If `const` is None, the `const` attribute of this object will be set to a `numpy.ndarray` of length `shape` filled with zeros.	`None`
`is_binary`	`bool`	A flag to determine if a leaf element is intended to be binary (0 or 1 in each dimension) or not. Defaults to `False`.	`False`

Raises:

Type	Description
`ValueError`	If all the coefficient matrices in the `decomposition_dict` doesn't have the same number of rows.
`ValueError`	If `const` is not one-dimensional.
`ValueError`	If the number of rows in `const` does not equal the number of rows in coefficient matrices in the `decomposition_dict`.

Source code in fomtools/linearexpression.py

def __init__(self, decomposition_dict: dict, const: np.ndarray = None, is_binary: bool = False):
    """
    Initialize a `LinearExpression` object with decomposition dictionary.

    Parameters
    ----------
    decomposition_dict : dict
        A mapping from each leaf `LinearExpression` to its coefficient matrix (an nxn sparse
        matrix).

    const : ndarray or None, optional
        A one-dimensional array or None (default). If `const` is None, the `const` attribute
        of this object will be set to a `numpy.ndarray` of length `shape` filled with zeros.

    is_binary : bool, optional
        A flag to determine if a leaf element is intended to be binary (0 or 1 in each dimension) or not. Defaults to `False`.

    Raises
    ------
    ValueError
        If all the coefficient matrices in the `decomposition_dict` doesn't have the same number
        of rows.

    ValueError
        If `const` is not one-dimensional.

    ValueError
        If the number of rows in `const` does not equal the number of rows in coefficient
        matrices in the `decomposition_dict`.
    """

    for leaf, mat in decomposition_dict.items():
        if not isinstance(leaf, LinearExpression) or not leaf.is_leaf:
            raise ValueError("Decomposition keys must be leaf expressions.")
        if len(mat.shape) != 2 or mat.shape[1] != leaf.ndim:
            raise ValueError(
                "Each coefficient must be a matrix with one column per leaf entry."
            )
    shapes = {mat.shape[0] for mat in decomposition_dict.values()}
    if len(shapes) > 1:
        raise ValueError(
            f"All coefficient matrices must have the same number of rows: {shapes}"
        )
    self.ndim = next(iter(shapes), 0)
    if const is not None:
        const = np.asarray(const, dtype=float)
        if const.ndim != 1:
            raise ValueError("The constant must be a one-dimensional vector.")
        if not shapes:
            self.ndim = const.size
        if const.shape != (self.ndim,):
            raise ValueError("The constant must have one entry per coefficient row.")
    self.const = np.zeros(self.ndim) if const is None else const
    self.decomposition_dict = decomposition_dict
    self.counter = LinearExpression.counter
    LinearExpression.counter += 1
    self.is_leaf = False
    self.is_binary = is_binary
    self.branch_priority = 0
    self.lb = [i.lb for i in decomposition_dict.keys()]
    self.ub = [i.ub for i in decomposition_dict.keys()]

le ¶

__le__(rhs: Union[Self, ndarray, list]) -> InequalityConstraint

Build a less-than-or-equality (<=) constraint between this expression and another LinearExpression object or numpy vector.`

Parameters:

Name	Type	Description	Default
`rhs`	`Union[Self, ndarray, list]`	The right-hand side of the inequalit. Scalars are broadcast to the shape of `self`. Arrays or expressions must be of same shape with `self`.	required

Returns:

Type	Description
`InequalityConstraint`	A constraint object representing `self <= rhs`.

Raises:

Type	Description
`TypeError`	If `rhs` is not a LinearExpression object, NumPy array or a list.
`ValueError`	If the shapes of `self` and `rhs` are not compatible (i.e., not equal and not broadcastable).

Notes

This method does not evaluate the inequality; it only builds a constraint for the solver.

Source code in fomtools/linearexpression.py

def __le__(self, rhs: Union[Self, np.ndarray, list]) -> InequalityConstraint:
    """
    Build a less-than-or-equality (`<=`) constraint between this expression and
    another `LinearExpression` object or numpy vector.`

    Parameters
    ----------
    rhs: LinearExpression, np.array, list
        The right-hand side of the inequalit. Scalars are broadcast to the shape of
        `self`. Arrays or expressions must be of same shape with `self`.

    Returns
    -------
    InequalityConstraint
        A constraint object representing `self <= rhs`.

    Raises
    ------
    TypeError
        If `rhs` is not a LinearExpression object, NumPy array or a list.

    ValueError
        If the shapes of `self` and `rhs` are not compatible (i.e., not equal and
        not broadcastable).

    Notes
    -----
    This method does not evaluate the inequality; it only builds a constraint
    for the solver.
    """
    return InequalityConstraint(self, rhs)

mul ¶

__mul__(scalar: Union[float, int]) -> Self

Multiply this LinearExpression object by a scalar.

Parameters:

Name	Type	Description	Default
`scalar`	`float or int`	The numeric factor to multiply each coefficient matrix by.	required

Returns:

Type	Description
`LinearExpression`	A new `LinearExpression` object in which each leaf’s coefficient matrix is multiplied by the given `scalar`.

Raises:

TypeError If the scalar is not an instance of int or float.

Source code in fomtools/linearexpression.py

def __mul__(self, scalar: Union[float, int]) -> Self:
    """
    Multiply this `LinearExpression` object by a scalar.

    Parameters
    ----------
    scalar : float or int
        The numeric factor to multiply each coefficient matrix by.

    Returns
    -------
    LinearExpression
        A new `LinearExpression` object in which each leaf’s coefficient matrix is multiplied
        by the given `scalar`.

    Raises:
    ------
    TypeError
        If the `scalar` is not an instance of int or float.

    """
    factor = np.asarray(scalar)
    if factor.ndim != 0 or not np.issubdtype(factor.dtype, np.number):
        raise TypeError(
            "LinearExpression multiplication requires a scalar; use a matrix @ expression for vector scaling."
        )
    factor = float(factor)
    return LinearExpression(
        {leaf: coeff * factor for leaf, coeff in self.decomposition_dict.items()},
        const=self.const * factor,
    )

neg ¶

__neg__() -> Self

Compute the negation of this LinearExpression.

This method is invoked for unary negation (e.g., -expr). It returns a new expression with each coefficient matrix in the decomposition multiplied by -1.

Returns:

Type	Description
`LinearExpression`	A new `LinearExpression` object with all coefficient matrices negated.

Source code in fomtools/linearexpression.py

def __neg__(self) -> Self:
    """
    Compute the negation of this LinearExpression.

    This method is invoked for unary negation (e.g., `-expr`). It returns a new
    expression with each coefficient matrix in the decomposition multiplied by -1.

    Returns
    -------
    LinearExpression
        A new `LinearExpression` object with all coefficient matrices negated.
    """
    return self * -1

radd ¶

__radd__(other: Union[Self, array, list]) -> Self

Reflected addition to support other + expression.

This method is invoked when a LinearExpression object appears on the right-hand side of a + operation (e.g. np.array([1,2,3]) + expr). It delegates to __add__, so that both np.array([1,2,3]) + expr and expr + np.array([1,2,3]) behave identically.

Parameters:

Name	Type	Description	Default
`other`	`(LinearExpression, array, list)`	The expression or a vector to add to this one.	required

Returns:

Type	Description
`LinearExpression`	A new `LinearExpression` object whose decomposition maps each leaf in the union of both expressiom to the sum of its coefficient matrices, treating any leaf missing from one operand as having a zero coefficient matrix.

Raises:

ValueError If the objects (LinearExpression or a vector) to be added together does not have the same dimension.

ValueError If the object to be added is not of one of the following types: LinearExpression, np.ndarray, or list.

Source code in fomtools/linearexpression.py

def __radd__(self, other: Union[Self, np.array, list]) -> Self:
    """
    Reflected addition to support other + expression.

    This method is invoked when a `LinearExpression` object appears on
    the right-hand side of a `+` operation (e.g. `np.array([1,2,3]) + expr`).
    It delegates to `__add__`, so that both `np.array([1,2,3]) + expr` and
    `expr + np.array([1,2,3])` behave identically.

    Parameters
    ----------
    other : LinearExpression, np.array, list
        The expression or a vector to add to this one.

    Returns
    -------
    LinearExpression
        A new `LinearExpression` object whose decomposition maps each leaf in the union of both
        expressiom to the sum of its coefficient matrices, treating any leaf missing from one
        operand as having a zero coefficient matrix.

    Raises:
    ------
    ValueError
        If the objects (`LinearExpression` or a vector) to be added together does not have
        the same dimension.

    ValueError
        If the object to be added is not of one of the following types: `LinearExpression`,
        `np.ndarray`, or `list`.
    """
    return self + other

rmatmul ¶

__rmatmul__(matrix: Union[ndarray, spmatrix]) -> Self

Multiply this LinearExpression object by another matrix.

This method is called when a LinearExpression appears on the right‐hand side of the @ operator (e.g., M @ expr).

Parameters:

Name	Type	Description	Default
`matrix`	`ndarray or spmatrix`	A matrix of shape `(m, n)`—where `n` is this expression’s dimension—to multiply on the left of each coefficient matrix.	required

Returns:

Type	Description
`LinearExpression`	A new `LinearExpression` object in which each leaf's coefficient matrix is multiplied by the given `matrix`.

Raises:

Type	Description
`TypeError`	If `other` is not a NumPy array or SciPy sparse matrix.
`ValueError`	If `other.shape[1]` does not match this expression’s dimension `n`.

Source code in fomtools/linearexpression.py

def __rmatmul__(self, matrix: Union[np.ndarray, spa.spmatrix]) -> Self:
    """
    Multiply this `LinearExpression` object by another matrix.

    This method is called when a `LinearExpression` appears on the right‐hand side
    of the `@` operator (e.g., `M @ expr`).

    Parameters
    ----------
    matrix : numpy.ndarray or scipy.sparse.spmatrix
        A matrix of shape `(m, n)`—where `n` is this expression’s dimension—to
        multiply on the left of each coefficient matrix.

    Returns
    -------
    LinearExpression
        A new `LinearExpression` object in which each leaf's coefficient matrix is
        multiplied by the given `matrix`.

    Raises
    ------
    TypeError
        If `other` is not a NumPy array or SciPy sparse matrix.
    ValueError
        If `other.shape[1]` does not match this expression’s dimension `n`.
    """

    if matrix.shape[1] != self.ndim:
        raise ValueError(
            f"""Matrix inner dimension ({matrix.shape[1]}) does not match
                the LinearExpression dimension ({self.ndim})"""
        )

    try:
        return LinearExpression(
            decomposition_dict={k: matrix @ v for k, v in self.decomposition_dict.items()},
            const=np.asarray(matrix @ self.const).ravel(),
        )
    except TypeError:
        raise TypeError(
            f"""Expected numpy.ndarray or scipy.sparse matrix for multiplication;
            got {type(matrix).__name__}. """
        )

rmul ¶

__rmul__(scalar: Union[float, int]) -> Self

Reflected multiplication to support scalar * expression.

This method is invoked when a LinearExpression object appears on the right-hand side of a * operation (e.g. 3 * expr). It delegates to to __mul__, so that both expr * 3 and 3 * expr behave identically.

Parameters:

Name	Type	Description	Default
`scalar`	`float or int`	The numeric factor to multiply each coefficient matrix by.	required

Returns:

Type	Description
`LinearExpression`	A new `LinearExpression` in which each leaf’s coefficient matrix is multiplied by the given `scalar`.

Raises:

TypeError If the scalar is not an instance of int or float.

Source code in fomtools/linearexpression.py

def __rmul__(self, scalar: Union[float, int]) -> Self:
    """
    Reflected multiplication to support scalar * expression.

    This method is invoked when a `LinearExpression` object appears on the
    right-hand side of a `*` operation (e.g. `3 * expr`). It delegates to
    to `__mul__`, so that both `expr * 3` and `3  * expr` behave identically.

    Parameters
    ----------
    scalar : float or int
        The numeric factor to multiply each coefficient matrix by.

    Returns
    -------
    LinearExpression
        A new `LinearExpression` in which each leaf’s coefficient matrix is multiplied
        by the given `scalar`.

    Raises:
    ------
    TypeError
        If the `scalar` is not an instance of int or float.
    """
    return self * scalar

rsub ¶

__rsub__(other: Self) -> Self

Reflected subtraction to support other - expression.

This method is invoked when a LinearExpression object appears on the right-hand side of a - operation (e.g. np.array([1,2,3]) - expr).

Parameters:

Name	Type	Description	Default
`other`	`(LinearExpression, array, list)`	The expression or a vector that this one is to be subtracted from.	required

Returns:

Type	Description
`LinearExpression`	A new `LinearExpression` object whose decomposition maps each leaf in the union of both expression to the difference of its coefficient matrices, treating any leaf missing from one operand as having a zero coefficient matrix.

Raises:

Type	Description
`ValueError`	If the two `LinearExpression` instances have mismatched dimensions.
`ValueError`	If the object to be subtracted is not of one of the following types: `LinearExpression`, `np.ndarray`, or `list`.

Source code in fomtools/linearexpression.py

def __rsub__(self, other: Self) -> Self:
    """
    Reflected subtraction to support other - expression.

    This method is invoked when a `LinearExpression` object appears on
    the right-hand side of a `-` operation (e.g. `np.array([1,2,3]) - expr`).

    Parameters
    ----------
    other : LinearExpression, np.array, list
        The expression or a vector that this one is to be subtracted from.

    Returns
    -------
    LinearExpression
        A new `LinearExpression` object whose decomposition maps each leaf in the union of
        both expression to the difference of its coefficient matrices, treating any leaf
        missing from one operand as having a zero coefficient matrix.

    Raises
    ------
    ValueError
        If the two `LinearExpression` instances have mismatched dimensions.

    ValueError
        If the object to be subtracted is not of one of the following types: `LinearExpression`,
        `np.ndarray`, or `list`.

    """
    return (-self) + other

sub ¶

__sub__(other: Self) -> Self

Subtract one LinearExpression from another.

Parameters:

Name	Type	Description	Default
`other`	`(LinearExpression, array, list)`	The expression or a vector xto subtract from this one.	required

Returns:

Type	Description
`LinearExpression`	A new `LinearExpression` object whose decomposition maps each leaf in the union of both expression to the difference of its coefficient matrices, treating any leaf missing from one operand as having a zero coefficient matrix.

Raises:

Type	Description
`ValueError`	If the two `LinearExpression` instances have mismatched dimensions.
`ValueError`	If the object to be subtracted is not of one of the following types: `LinearExpression`, `np.ndarray`, or `list`.

Source code in fomtools/linearexpression.py

def __sub__(self, other: Self) -> Self:
    """
    Subtract one LinearExpression from another.

    Parameters
    ----------
    other : LinearExpression, np.array, list
        The expression or a vector xto subtract from this one.

    Returns
    -------
    LinearExpression
        A new `LinearExpression` object whose decomposition maps each leaf in the union of
        both expression to the difference of its coefficient matrices, treating any leaf
        missing from one operand as having a zero coefficient matrix.

    Raises
    ------
    ValueError
        If the two `LinearExpression` instances have mismatched dimensions.

    ValueError
        If the object to be subtracted is not of one of the following types: `LinearExpression`,
        `np.ndarray`, or `list`.

    """
    result = self + (-other)
    if isinstance(other, LinearExpression):
        result._difference = (self, other)
    return result

truediv ¶

__truediv__(scalar: Union[float, int]) -> Self

Divide this LinearExpression by a scalar factor.

This method is invoked when the expression appears on the left-hand side of a true division (e.g. expr / 3).

Parameters:

Name	Type	Description	Default
`scalar`	`float or int`	The numeric divisor to apply to every coefficient matrix.	required

Returns:

Type	Description
`LinearExpression`	A new `LinearExpression` in which each leaf's coefficient matrix is divided by the given `scalar`.

Raises:

Type	Description
`TypeError`	If the `scalar` is not an instance of int or float.
`ZeroDivisionError`	If `scalar` is zero.

Source code in fomtools/linearexpression.py

def __truediv__(self, scalar: Union[float, int]) -> Self:
    """
    Divide this LinearExpression by a scalar factor.

    This method is invoked when the expression appears on the left-hand side
    of a true division (e.g. `expr / 3`).

    Parameters
    ----------
    scalar : float or int
        The numeric divisor to apply to every coefficient matrix.

    Returns
    -------
    LinearExpression
        A new `LinearExpression` in which each leaf's coefficient matrix is divided
        by the given `scalar`.

    Raises
    ------
    TypeError
        If the `scalar` is not an instance of int or float.

    ZeroDivisionError
        If `scalar` is zero.
    """
    if scalar == 0:
        raise ZeroDivisionError("Division of LinearExpression by zero is not allowed.")

    return self * (1 / scalar)

bound_propagation ¶

bound_propagation() -> tuple[ndarray, ndarray]

Compute the elementwise lower and upper bounds of a linear expression given the bound constraints of its coefficient matrices.

Returns:

Type	Description
`tuple[ndarray, ndarray]`	A pair (lower, upper) representing the elementwise lower and upper bounds of the evaluated expression.

Raises:

Type	Description
`ValueError`	If any computed lower bound exceeds its corresponding upper bound.

Source code in fomtools/linearexpression.py

def bound_propagation(self) -> tuple[np.ndarray, np.ndarray]:
    """
    Compute the elementwise lower and upper bounds of a linear expression
    given the bound constraints of its coefficient matrices.

    Returns
    -------
    tuple[np.ndarray, np.ndarray]
        A pair (lower, upper) representing the elementwise lower and upper
        bounds of the evaluated expression.

    Raises
    ------
    ValueError
        If any computed lower bound exceeds its corresponding upper bound.
    """

    def _interval_bound_propagation(
        a: np.matrix, lb: np.ndarray, ub: np.ndarray
    ) -> tuple[np.ndarray, np.ndarray]:
        """
        Bounds the linear image y = A @ x for any x with lb ≤ x ≤ ub.

        Using midpoint m = (ub + lb)/2 and radius r = (ub - lb)/2:
            y_min = A @ m - |A| @ r
            y_max = A @ m + |A| @ r

        Returns (y_min, y_max).

        References
        ----------
            .. S. Gowal, K. Dvijotham, R. Stanforth, R. Bunel, C. Qin, J. Uesato, R. Arand-
               jelovi´c, T. Mann, and Sigma. Kohli. "On the effectiveness of interval bound propa-
               gation for training verifiably robust models. arXiv:1810.12715, 2018."
        """
        if np.all(np.isfinite(lb)) and np.all(np.isfinite(ub)):
            return (a @ (ub + lb) - np.abs(a) @ (ub - lb)) / 2, (
                a @ (ub + lb) + np.abs(a) @ (ub - lb)
            ) / 2
        # An infinite bound (e.g. the unbounded output leaf of a linear
        # solve) makes the midpoint inf - inf = NaN, and the NaN then
        # spreads to every later bound. Split A into its positive and
        # negative parts and propagate the finite and infinite parts
        # separately, with the interval convention 0 * inf = 0.
        if spa.issparse(a):
            pos, neg = a.maximum(0), a.minimum(0)
        else:
            pos, neg = np.maximum(a, 0), np.minimum(a, 0)
        lb_f = np.where(np.isfinite(lb), lb, 0.0)
        ub_f = np.where(np.isfinite(ub), ub, 0.0)
        lo = pos @ lb_f + neg @ ub_f
        hi = pos @ ub_f + neg @ lb_f
        to_minus_inf = pos @ np.isneginf(lb).astype(float) - neg @ np.isposinf(ub).astype(float)
        to_plus_inf = pos @ np.isposinf(ub).astype(float) - neg @ np.isneginf(lb).astype(float)
        lo = np.where(np.asarray(to_minus_inf) > 0, -np.inf, lo)
        hi = np.where(np.asarray(to_plus_inf) > 0, np.inf, hi)
        return lo, hi

    out_lb, out_ub = np.zeros(self.ndim), np.zeros(self.ndim)
    for k, v in self.decomposition_dict.items():
        # Check the leaf bounds too: the infinite-bound path would read a NaN as 0.
        _reject_nan_bounds(k.lb, k.ub)
        _lb, _ub = _interval_bound_propagation(v, k.lb, k.ub)

        _reject_nan_bounds(_lb, _ub)
        if np.any(_lb > _ub):
            raise ValueError("Lower bound cannot exceed upper bound .")

        out_lb += _lb
        out_ub += _ub

    # Add constant term to bounds
    out_lb += self.const
    out_ub += self.const

    return out_lb, out_ub

from_int `classmethod` ¶

from_int(ndim: int, is_binary: bool = False, lb: float = -inf, ub: float = inf, branch_priority: int = 0) -> Self

Initialize a LinearExpression object with an integer shape. Internally, this creates a decomposition dictionary that maps the LinearExpression object with a sparse identity matrix of shape (shape, shape).

Parameters:

Name	Type	Description	Default
`ndim`	`int`	The dimension of underlying space, i.e., the size of each coefficient matrix.	required
`is_binary`	`bool`	Flag to determine if the leaf expression is binary or not (0 or 1 in each dimension).	`False`
`branch_priority`	`int`	Branching priority hint for a binary leaf: branch-and-bound solvers that support priorities branch on higher values first. Solvers without such a notion ignore it.	`0`

Returns:

Type	Description
`LinearExpression`	A new `LinearExpression` instance whose decomposition contains a single entry: the instance itself as a key, and a SciPy sparse identity matrix of shape `(shape, shape)` as the value.

Source code in fomtools/linearexpression.py

@classmethod
def from_int(
    cls,
    ndim: int,
    is_binary: bool = False,
    lb: float = -np.inf,
    ub: float = np.inf,
    branch_priority: int = 0,
) -> Self:
    """
    Initialize a `LinearExpression` object with an integer `shape`. Internally, this
    creates a decomposition dictionary that maps the `LinearExpression` object with a sparse
    identity matrix of shape `(shape, shape)`.

    Parameters
    ----------
    ndim : int
        The dimension of underlying space, i.e., the size of each coefficient matrix.
    is_binary: bool
        Flag to determine if the leaf expression is binary or not (0 or 1 in each dimension).
    branch_priority: int, default 0
        Branching priority hint for a binary leaf: branch-and-bound solvers that
        support priorities branch on higher values first. Solvers without such
        a notion ignore it.

    Returns
    -------
    LinearExpression
        A new `LinearExpression` instance whose decomposition contains a single
        entry: the instance itself as a key, and a SciPy sparse identity matrix of
        shape `(shape, shape)` as the value.
    """
    _reject_nan_bounds(lb, ub)
    obj = cls.__new__(cls)  # uninitialized instance
    obj.is_leaf = True
    obj.decomposition_dict = {obj: spa.eye(ndim)}
    obj.ndim = ndim
    obj.counter = cls.counter
    obj.const = np.zeros(ndim)
    obj.is_binary = is_binary
    obj.branch_priority = branch_priority
    obj.lb = np.zeros(ndim) if is_binary else np.full(ndim, lb, dtype=float)
    obj.ub = np.ones(ndim) if is_binary else np.full(ndim, ub, dtype=float)
    cls.counter += 1
    return obj

update_bounds ¶

update_bounds(lb: ndarray, ub: ndarray) -> None

Update lower and upper bounds of the LinearExpression objects.

Source code in fomtools/linearexpression.py

def update_bounds(self, lb: np.ndarray, ub: np.ndarray) -> None:
    """Update lower and upper bounds of the `LinearExpression` objects."""
    _reject_nan_bounds(lb, ub)
    self.lb = np.maximum(self.lb, lb)
    self.ub = np.minimum(self.ub, ub)

Linear expressions¶