List of bridges

This section describes the Bridges.AbstractBridges that are implemented in MathOptInterface.

Constraint bridges

These bridges are subtyptes of Bridges.Constraint.AbstractBridge.

MathOptInterface.Bridges.Constraint.VectorizeBridgeType
VectorizeBridge{T,F,S,G} <: Bridges.Constraint.AbstractBridge

VectorizeBridge implements the following reformulations:

  • $g(x) \ge a$ into $[g(x) - a] \in \mathbb{R}_+$
  • $g(x) \le a$ into $[g(x) - a] \in \mathbb{R}_-$
  • $g(x) == a$ into $[g(x) - a] \in \{0\}$

where T is the coefficient type of g(x) - a.

Source node

VectorizeBridge supports:

Target nodes

VectorizeBridge creates:

MathOptInterface.Bridges.Constraint.ScalarizeBridgeType
ScalarizeBridge{T,F,S}

ScalarizeBridge implements the following reformulations:

  • $f(x) - a \in \mathbb{R}_+$ into $f_i(x) \ge a_i$ for all $i$
  • $f(x) - a \in \mathbb{R}_-$ into $f_i(x) \le a_i$ for all $i$
  • $f(x) - a \in \{0\}$ into $f_i(x) == a_i$ for all $i$

Source node

ScalarizeBridge supports:

Target nodes

ScalarizeBridge creates:

MathOptInterface.Bridges.Constraint.SplitIntervalBridgeType
SplitIntervalBridge{T,F,S,LS,US} <: Bridges.Constraint.AbstractBridge

SplitIntervalBridge implements the following reformulations:

  • $l \le f(x) \le u$ into $f(x) \ge l$ and $f(x) \le u$
  • $f(x) = b$ into $f(x) \ge b$ and $f(x) \le b$
  • $f(x) \in \{0\}$ into $f(x) \in \mathbb{R}_+$ and $f(x) \in \mathbb{R}_-$

Source node

SplitIntervalBridge supports:

Target nodes

SplitIntervalBridge creates:

or

Note

If T<:AbstractFloat and S is MOI.Interval{T} then no lower (resp. upper) bound constraint is created if the lower (resp. upper) bound is typemin(T) (resp. typemax(T)). Similarly, when MOI.ConstraintSet is set, a lower or upper bound constraint may be deleted or created accordingly.

MathOptInterface.Bridges.Constraint.SOCtoRSOCBridgeType
SOCtoRSOCBridge{T,F,G} <: Bridges.Constraint.AbstractBridge

SOCtoRSOCBridge implements the following reformulation:

  • $||x||_2 \le t$ into $2uv \ge ||w||_2^2$, with the substitution rules $t = \frac{u}{\sqrt 2} + \frac{v}{\sqrt 2}$, $x = (\frac{u}{\sqrt 2} - \frac{v}{\sqrt 2}, w)$.

Assumptions

  • SOCtoRSOCBridge assumes that $|x| \ge 1$.

Source node

SOCtoRSOCBridge supports:

Target node

SOCtoRSOCBridge creates:

MathOptInterface.Bridges.Constraint.RSOCtoSOCBridgeType
RSOCtoSOCBridge{T,F,G} <: Bridges.Constraint.AbstractBridge

RSOCtoSOCBridge implements the following reformulation:

  • $||x||_2^2 \le 2tu$ into $||v|| \le w$, with the substitution rules $t = \frac{w}{\sqrt 2} + \frac{v_1}{\sqrt 2}$, $u = \frac{w}{\sqrt 2} - \frac{v_1}{\sqrt 2}$, and $x = (v_2,\ldots,v_N)$.

Source node

RSOCtoSOCBridge supports:

Target node

RSOCtoSOCBridge creates:

MathOptInterface.Bridges.Constraint.SOCtoNonConvexQuadBridgeType
SOCtoNonConvexQuadBridge{T} <: Bridges.Constraint.AbstractBridge

SOCtoNonConvexQuadBridge implements the following reformulations:

  • $||x||_2 \le t$ into $\sum x^2 - t^2 \le 0$ and $1t + 0 \ge 0$

The MOI.ScalarAffineFunction $1t + 0$ is used in case the variable has other bound constraints.

Warning

This transformation starts from a convex constraint and creates a non-convex constraint. Unless the solver has explicit support for detecting second-order cones in quadratic form, this may (wrongly) be interpreted by the solver as being non-convex. Therefore, this bridge is not added automatically by MOI.Bridges.full_bridge_optimizer. Care is recommended when adding this bridge to a optimizer.

Source node

SOCtoNonConvexQuadBridge supports:

Target nodes

SOCtoNonConvexQuadBridge creates:

MathOptInterface.Bridges.Constraint.RSOCtoNonConvexQuadBridgeType
RSOCtoNonConvexQuadBridge{T} <: Bridges.Constraint.AbstractBridge

RSOCtoNonConvexQuadBridge implements the following reformulations:

  • $||x||_2 \le t \cdot u$ into $\sum x^2 - t\cdot u \le 0$, $1t + 0 \ge 0$, and $1u + 0 \ge 0$.

The MOI.ScalarAffineFunctions $1t + 0$ and $1u + 0$ are used in case the variables have other bound constraints.

Warning

This transformation starts from a convex constraint and creates a non-convex constraint. Unless the solver has explicit support for detecting rotated second-order cones in quadratic form, this may (wrongly) be interpreted by the solver as being non-convex. Therefore, this bridge is not added automatically by MOI.Bridges.full_bridge_optimizer. Care is recommended when adding this bridge to a optimizer.

Source node

RSOCtoNonConvexQuadBridge supports:

Target nodes

RSOCtoNonConvexQuadBridge creates:

MathOptInterface.Bridges.Constraint.QuadtoSOCBridgeType
QuadtoSOCBridge{T} <: Bridges.Constraint.AbstractBridge

QuadtoSOCBridge converts quadratic inequalities

\[\frac{1}{2}x^T Q x + a^T x + b \le 0\]

into MOI.RotatedSecondOrderCone constraints, but it only applies when $Q$ is positive semidefinite.

This is because, if Q is positive semidefinite, there exists U such that $Q = U^T U$, and so the inequality can then be rewritten as;

\[\|U x\|_2^2 \le 2 (-a^T x - b)\]

Therefore, QuadtoSOCBridge implements the following reformulation:

  • $\frac{1}{2}x^T Q x + a^T x + b \le 0$ into $(1, -a^T x - b, Ux) \in RotatedSecondOrderCone$

Source node

QuadtoSOCBridge supports:

Target nodes

RelativeEntropyBridge creates:

MathOptInterface.Bridges.Constraint.SOCtoPSDBridgeType
SOCtoPSDBridge{T,F,G} <: Bridges.Constraint.AbstractBridge

SOCtoPSDBridge implements the following reformulation:

  • $||x||_2 \le t$ into $\left[\begin{array}{c c}t & x^\top \\ x & t \mathbf{I}\end{array}\right]$
Warning

This bridge is not added by default by MOI.Bridges.full_bridge_optimizer because bridging second order cone constraints to semidefinite constraints can be achieved by the SOCtoRSOCBridge followed by the RSOCtoPSDBridge, while creating a smaller semidefinite constraint.

Source node

SOCtoPSDBridge supports:

Target nodes

SOCtoPSDBridge creates:

MathOptInterface.Bridges.Constraint.GeoMeantoRelEntrBridgeType
GeoMeantoRelEntrBridge{T,F,G,H} <: Bridges.Constraint.AbstractBridge

GeoMeantoRelEntrBridge implements the following reformulation:

  • $(u, w) \in GeometricMeanCone$ into $(0, w, (u + y)\mathbf{1})\in RelativeEntropyCone$ and $y \ge 0$

Source node

GeoMeantoRelEntrBridge supports:

Target nodes

GeoMeantoRelEntrBridge creates:

Derivation

The derivation of the bridge is as follows:

\[\begin{aligned} (u, w) \in GeometricMeanCone \iff & u \le \left(\prod_{i=1}^n w_i\right)^{1/n} \\ \iff & 0 \le u + y \le \left(\prod_{i=1}^n w_i\right)^{1/n}, y \ge 0 \\ \iff & 1 \le \frac{\left(\prod_{i=1}^n w_i\right)^{1/n}}{u + y}, y \ge 0 \\ \iff & 1 \le \left(\prod_{i=1}^n \frac{w_i}{u + y}\right)^{1/n}, y \ge 0 \\ \iff & 0 \le \sum_{i=1}^n \log\left(\frac{w_i}{u + y}\right), y \ge 0 \\ \iff & 0 \ge \sum_{i=1}^n \log\left(\frac{u + y}{w_i}\right), y \ge 0 \\ \iff & 0 \ge \sum_{i=1}^n (u + y) \log\left(\frac{u + y}{w_i}\right), y \ge 0 \\ \iff & (0, w, (u + y)\mathbf{1}) \in RelativeEntropyCone, y \ge 0 \\ \end{aligned}\]

This derivation assumes that $u + y > 0$, which is enforced by the relative entropy cone.

MathOptInterface.Bridges.Constraint.GeoMeanBridgeType
GeoMeanBridge{T,F,G,H} <: Bridges.Constraint.AbstractBridge

GeoMeanBridge implements a reformulation from MOI.GeometricMeanCone into MOI.RotatedSecondOrderCone.

The reformulation is best described in an example.

Consider the cone of dimension 4:

\[t \le \sqrt[3]{x_1 x_2 x_3}\]

This can be rewritten as $\exists y \ge 0$ such that:

\[\begin{align*} t & \le y,\\ y^4 & \le x_1 x_2 x_3 y. \end{align*}\]

Note that we need to create $y$ and not use $t^4$ directly because $t$ is allowed to be negative.

This is equivalent to:

\[\begin{align*} t & \le \frac{y_1}{\sqrt{4}},\\ y_1^2 & \le 2y_2 y_3,\\ y_2^2 & \le 2x_1 x_2, \\ y_3^2 & \le 2x_3(y_1/\sqrt{4}) \\ y \ge 0. \end{align*}\]

More generally, you can show how the geometric mean code is recursively expanded into a set of new variables $y$ in MOI.Nonnegatives, a set of MOI.RotatedSecondOrderCone constraints, and a MOI.LessThan constraint between $t$ and $y_1$.

Source node

GeoMeanBridge supports:

Target nodes

GeoMeanBridge creates:

MathOptInterface.Bridges.Constraint.RelativeEntropyBridgeType
RelativeEntropyBridge{T,F,G,H} <: Bridges.Constraint.AbstractBridge

RelativeEntropyBridge implements the following reformulation that converts a MOI.RelativeEntropyCone into an MOI.ExponentialCone:

  • $u \ge \sum_{i=1}^n w_i \log \left(\frac{w_i}{v_i}\right)$ into $y_i \ge 0$, $\sum_{i=1}^n y_i$, and $(-y_i, w_i, v_i) \in ExponentialCone$.

Source node

RelativeEntropyBridge supports:

Target nodes

RelativeEntropyBridge creates:

MathOptInterface.Bridges.Constraint.SquareBridgeType
SquareBridge{T, F<:MOI.AbstractVectorFunction,
             G<:MOI.AbstractScalarFunction,
             TT<:MOI.AbstractSymmetricMatrixSetTriangle,
             ST<:MOI.AbstractSymmetricMatrixSetSquare} <: AbstractBridge

The SquareBridge reformulates the constraint of a square matrix to be in ST to a list of equality constraints for pair or off-diagonal entries with different expressions and a TT constraint the upper triangular part of the matrix.

For instance, the constraint for the matrix

\[\begin{pmatrix} 1 & 1 + x & 2 - 3x\\ 1 + x & 2 + x & 3 - x\\ 2 - 3x & 2 + x & 2x \end{pmatrix}\]

to be PSD can be broken down to the constraint of the symmetric matrix

\[\begin{pmatrix} 1 & 1 + x & 2 - 3x\\ \cdot & 2 + x & 3 - x\\ \cdot & \cdot & 2x \end{pmatrix}\]

and the equality constraint between the off-diagonal entries (2, 3) and (3, 2) $2x == 1$. Note that now symmetrization constraint need to be added between the off-diagonal entries (1, 2) and (2, 1) or between (1, 3) and (3, 1) since the expressions are the same.

MathOptInterface.Bridges.Constraint.RootDetBridgeType
RootDetBridge{T,F,G,H} <: Bridges.Constraint.AbstractBridge

The MOI.RootDetConeTriangle is representable by MOI.PositiveSemidefiniteConeTriangle and MOI.GeometricMeanCone constraints, see [1, p. 149].

Indeed, $t \le \det(X)^{1/n}$ if and only if there exists a lower triangular matrix $Δ$ such that:

\[\begin{align*} \begin{pmatrix} X & Δ\\ Δ^\top & \mathrm{Diag}(Δ) \end{pmatrix} & \succeq 0\\ (t, \mathrm{Diag}(Δ)) in GeometricMeanCone \end{align*}\]

Source node

RootDetBridge supports:

Target nodes

RootDetBridge creates:

[1] Ben-Tal, Aharon, and Arkadi Nemirovski. Lectures on modern convex optimization: analysis, algorithms, and engineering applications. Society for Industrial and Applied Mathematics, 2001.

MathOptInterface.Bridges.Constraint.LogDetBridgeType
LogDetBridge{T,F,G,H,I} <: Bridges.Constraint.AbstractBridge

The MOI.LogDetConeTriangle is representable by MOI.PositiveSemidefiniteConeTriangle and MOI.ExponentialCone constraints.

Indeed, $\log\det(X) = \sum\limits_{i=1}^n \log(\delta_i)$ where $\delta_i$ are the eigenvalues of $X$.

Adapting the method from [1, p. 149], we see that $t \le u \log(\det(X/u))$ for $u > 0$ if and only if there exists a lower triangular matrix $Δ$ such that

\[\begin{align*} \begin{pmatrix} X & Δ\\ Δ^\top & \mathrm{Diag}(Δ) \end{pmatrix} & \succeq 0\\ t - \sum_{i=1}^n u \log(Δ_{ii}/u) & \le 0 \end{align*}\]

Which we reformulate further into

\[\begin{align*} \begin{pmatrix} X & Δ\\ Δ^\top & \mathrm{Diag}(Δ) \end{pmatrix} & \succeq 0\\ (l_i, u , Δ_{ii}) in ExponentialCone & \forall i \\ t - \sum_{i=1}^n l_i & \le 0 \end{align*}\]

Source node

LogDetBridge supports:

Target nodes

LogDetBridge creates:

[1] Ben-Tal, Aharon, and Arkadi Nemirovski. Lectures on modern convex optimization: analysis, algorithms, and engineering applications. Society for Industrial and Applied Mathematics, 2001.

MathOptInterface.Bridges.Constraint.IndicatorActiveOnFalseBridgeType
IndicatorActiveOnFalseBridge{T,F,S} <: Bridges.Constraint.AbstractBridge

IndicatorActiveOnFalseBridge implements the following reformulation:

  • $!z \implies {f(x) \in S}$ into $y \implies {f(x) \in S}$, $z + y == 1$, and $y \in \{0, \}$

Source node

IndicatorActiveOnFalseBridge supports:

Target nodes

IndicatorActiveOnFalseBridge creates:

MathOptInterface.Bridges.Constraint.IndicatorSOS1BridgeType
IndicatorSOS1Bridge{T,S} <: Bridges.Constraint.AbstractBridge

IndicatorSOS1Bridge implements the following reformulation:

  • $z \implies {f(x) \in S}$ into $f(x) + y \in S$, $SOS1(y, z)$
Warning

This bridge assumes that the solver supports MOI.SOS1{T} constraints in which one of the variables ($y$) is continuous.

Source node

IndicatorSOS1Bridge supports:

Target nodes

IndicatorSOS1Bridge creates:

MathOptInterface.Bridges.Constraint.SemiToBinaryBridgeType
SemiToBinaryBridge{T,S} <: Bridges.Constraint.AbstractBridge

SemiToBinaryBridge implements the following reformulations:

  • $x \in \{0\} \cup [l, u]$ into

    \[\begin{aligned} x \leq z \times u \ x \geq z \times l \ z \in \{0, 1\} \end{aligned}\]

  • $x \in \{0\} \cup \{l, \ldots, u\}$ into

    \[\begin{aligned} x \leq z \times u \ x \geq z \times l \ z \in \{0, 1\} \ x \in \mathbb{Z} \end{aligned}\]

Source node

SemiToBinaryBridge supports:

Target nodes

SemiToBinaryBridge creates:

Objective bridges

These bridges are subtyptes of Bridges.Objective.AbstractBridge.

MathOptInterface.Bridges.Objective.SlackBridgeType
SlackBridge{T,F,G}

SlackBridge implements the following reformulations:

  • $\min\{f(x)\}$ into $\min\{y\;|\; f(x) - y \le 0\}$
  • $\max\{f(x)\}$ into $\max\{y\;|\; f(x) - y \ge 0\}$

where F is the type of f(x) - y, G is the type of f(x), and T is the coefficient type of f(x).

Source node

SlackBridge supports:

Target nodes

SlackBridge creates:

Warning

When using this bridge, changing the optimization sense is not supported. Set the sense to MOI.FEASIBILITY_SENSE first to delete the bridge, then set MOI.ObjectiveSense and re-add the objective.

Variable bridges

These bridges are subtyptes of Bridges.Variable.AbstractBridge.

MathOptInterface.Bridges.Variable.RSOCtoPSDBridgeType
RSOCtoPSDBridge{T} <: Bridges.Variable.AbstractBridge

RSOCtoPSDBridge implements the following reformulation:

  • $||x||_2^2 \le 2tu$ where $t, u \ge 0$ into $Y \succeq 0$, with the substitution rule: $Y = \left[\begin{array}{c c}t & x^\top \\ x & 2u \mathbf{I}\end{array}\right].$

Additional bounds are added to ensure the off-diagonals of the $2uI$ submatrix are 0, and linear constraints are added to ennsure the diagonal of $2uI$ takes the same values.

As a special case, if $|x|| = 0$, then RSOCtoPSDBridge reformulates into $(t, u) \in \mathbb{R}_+$.

Source node

RSOCtoPSDBridge supports:

Target nodes

RSOCtoPSDBridge creates:

MathOptInterface.Bridges.Variable.RSOCtoSOCBridgeType
RSOCtoSOCBridge{T} <: Bridges.Variable.AbstractBridge

RSOCtoSOCBridge implements the following reformulation:

  • $||x||_2^2 \le 2tu$ into $||v|| \le w$, with the substitution rules $t = \frac{w}{\sqrt 2} + \frac{v_1}{\sqrt 2}$, $u = \frac{w}{\sqrt 2} - \frac{v_1}{\sqrt 2}$, and $x = (v_2,\ldots,v_N)$.

Source node

RSOCtoSOCBridge supports:

Target node

RSOCtoSOCBridge creates:

MathOptInterface.Bridges.Variable.SOCtoRSOCBridgeType
SOCtoRSOCBridge{T} <: Bridges.Variable.AbstractBridge

SOCtoRSOCBridge implements the following reformulation:

  • $||x||_2 \le t$ into $2uv \ge ||w||_2^2$, with the substitution rules $t = \frac{u}{\sqrt 2} + \frac{v}{\sqrt 2}$, $x = (\frac{u}{\sqrt 2} - \frac{v}{\sqrt 2}, w)$.

Assumptions

  • SOCtoRSOCBridge assumes that $|x| \ge 1$.

Source node

SOCtoRSOCBridge supports:

Target node

SOCtoRSOCBridge creates:

MathOptInterface.Bridges.Variable.VectorizeBridgeType
VectorizeBridge{T,S} <: Bridges.Variable.AbstractBridge

VectorizeBridge implements the following reformulations:

  • $x \ge a$ into $[y] \in \mathbb{R}_+$ with the substitution rule $x = a + y$
  • $x \le a$ into $[y] \in \mathbb{R}_-$ with the substitution rule $x = a + y$
  • $x == a$ into $[y] \in \{0\}$ with the substitution rule $x = a + y$

where T is the coefficient type of a + y.

Source node

VectorizeBridge supports:

Target nodes

VectorizeBridge creates:

MathOptInterface.Bridges.Variable.ZerosBridgeType
ZerosBridge{T} <: Bridges.Variable.AbstractBridge

ZerosBridge implements the following reformulation:

  • $x \in \{0\}$ into the substitution rule $x = 0$,

where T is the coefficient type of 0.

Source node

ZerosBridge supports:

Target nodes

ZerosBridge does not create target nodes. It replaces all instances of x with 0 via substitution. This means that no variables are created in the underlying model.

Caveats

The bridged variables are similar to parameters with zero values. Parameters with non-zero values can be created with constrained variables in MOI.EqualTo by combining a VectorizeBridge and this bridge.

However, functions modified by ZerosBridge cannot be unbridged. That is, for a given function, we cannot determine if the bridged variables were used.

A related implication is that this bridge does not support MOI.ConstraintDual. However, if a MOI.Utilities.CachingOptimizer is used, the dual can be determined by the bridged optimizer using MOI.Utilities.get_fallback because the caching optimizer records the unbridged function.