# List of bridges

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

## Constraint bridges

These bridges are subtypes of Bridges.Constraint.AbstractBridge.

MathOptInterface.Bridges.Constraint.AbstractToIntervalBridgeType
AbstractToIntervalBridge{T<:AbstractFloat,S,F}

An abstract type that simplifies the creation of other bridges.

Warning

T must be a AbstractFloat type because otherwise typemin and typemax would either be not implemented (for example, BigInt), or would not give infinite value (for example, Int). For this reason, this bridge is only added to MOI.Bridges.full_bridge_optimizer when T is a subtype of AbstractFloat.

source
MathOptInterface.Bridges.Constraint.AllDifferentToCountDistinctBridgeType
AllDifferentToCountDistinctBridge{T,F} <: Bridges.Constraint.AbstractBridge

AllDifferentToCountDistinctBridge implements the following reformulations:

• $x \in \textsf{AllDifferent}(d)$ to $(n, x) \in \textsf{CountDistinct}(1+d)$ and $n = d$
• $f(x) \in \textsf{AllDifferent}(d)$ to $(d, f(x)) \in \textsf{CountDistinct}(1+d)$

Source node

AllDifferentToCountDistinctBridge supports:

where F is MOI.VectorOfVariables or MOI.VectorAffineFunction{T}.

Target nodes

AllDifferentToCountDistinctBridge creates:

source
MathOptInterface.Bridges.Constraint.BinPackingToMILPBridgeType
BinPackingToMILPBridge{T,F} <: Bridges.Constraint.AbstractBridge

BinPackingToMILPBridge implements the following reformulation:

• $x \in BinPacking(c, w)$ into a mixed-integer linear program.

Reformulation

The reformulation is non-trivial, and it depends on the finite domain of each variable $x_i$, which we as define $S_i = \{l_i,\ldots,u_i\}$.

First, we introduce new binary variables $z_{ij}$, which are $1$ if variable $x_i$ takes the value $j$ in the optimal solution and $0$ otherwise:

\begin{aligned} z_{ij} \in \{0, 1\} & \;\; \forall i \in 1\ldots d, j \in S_i \\ x_i - \sum\limits_{j\in S_i} j \cdot z_{ij} = 0 & \;\; \forall i \in 1\ldots d \\ \sum\limits_{j\in S_i} z_{ij} = 1 & \;\; \forall i \in 1\ldots d \\ \end{aligned}

Then, we add the capacity constraint for all possible bins $j$:

$$$\sum\limits_{i} w_i z_{ij} \le c \forall j \in \bigcup_{i=1,\ldots,d} S_i$$$

Source node

BinPackingToMILPBridge supports:

Target nodes

BinPackingToMILPBridge creates:

source
MathOptInterface.Bridges.Constraint.CircuitToMILPBridgeType
CircuitToMILPBridge{T,F} <: Bridges.Constraint.AbstractBridge

CircuitToMILPBridge implements the following reformulation:

• $x \in \textsf{Circuit}(d)$ to the Miller-Tucker-Zemlin formulation of the Traveling Salesperson Problem.

Source node

CircuitToMILPBridge supports:

where F is MOI.VectorOfVariables or MOI.VectorAffineFunction{T}.

Target nodes

CircuitToMILPBridge creates:

source
MathOptInterface.Bridges.Constraint.ComplexNormInfinityToSecondOrderConeBridgeType
ComplexNormInfinityToSecondOrderConeBridge{T} <: Bridges.Constraint.AbstractBridge

ComplexNormInfinityToSecondOrderConeBridge implements the following reformulation:

• $(t, x) \in NormInfinity(1+d)$ into $(t, real(x_i), imag(x_i)) \in SecondOrderCone()$ for all $i$.

Source node

ComplexNormInfinityToSecondOrderConeBridge supports:

Target nodes

ComplexNormInfinityToSecondOrderConeBridge creates:

source
MathOptInterface.Bridges.Constraint.CountAtLeastToCountBelongsBridgeType
CountAtLeastToCountBelongsBridge{T,F} <: Bridges.Constraint.AbstractBridge

CountAtLeastToCountBelongsBridge implements the following reformulation:

• $x \in \textsf{CountAtLeast}(n, d, \mathcal{S})$ to $(n_i, x_{d_i}) \in \textsf{CountBelongs}(1+d, \mathcal{S})$ and $n_i \ge n$ for all $i$.

Source node

CountAtLeastToCountBelongsBridge supports:

where F is MOI.VectorOfVariables or MOI.VectorAffineFunction{T}.

Target nodes

CountAtLeastToCountBelongsBridge creates:

source
MathOptInterface.Bridges.Constraint.CountBelongsToMILPBridgeType
CountBelongsToMILPBridge{T,F} <: Bridges.Constraint.AbstractBridge

CountBelongsToMILPBridge implements the following reformulation:

• $(n, x) \in \textsf{CountBelongs}(1+d, \mathcal{S})$ into a mixed-integer linear program.

Reformulation

The reformulation is non-trivial, and it depends on the finite domain of each variable $x_i$, which we as define $S_i = \{l_i,\ldots,u_i\}$.

First, we introduce new binary variables $z_{ij}$, which are $1$ if variable $x_i$ takes the value $j$ in the optimal solution and $0$ otherwise:

\begin{aligned} z_{ij} \in \{0, 1\} & \;\; \forall i \in 1\ldots d, j \in S_i \\ x_i - \sum\limits_{j\in S_i} j \cdot z_{ij} = 0 & \;\; \forall i \in 1\ldots d \\ \sum\limits_{j\in S_i} z_{ij} = 1 & \;\; \forall i \in 1\ldots d \\ \end{aligned}

Finally, $n$ is constrained to be the number of $z_{ij}$ elements that are in $\mathcal{S}$:

$$$n - \sum\limits_{i\in 1\ldots d, j \in \mathcal{S}} z_{ij} = 0$$$

Source node

CountBelongsToMILPBridge supports:

where F is MOI.VectorOfVariables or MOI.VectorAffineFunction{T}.

Target nodes

CountBelongsToMILPBridge creates:

source
MathOptInterface.Bridges.Constraint.CountDistinctToMILPBridgeType
CountDistinctToMILPBridge{T,F} <: Bridges.Constraint.AbstractBridge

CountDistinctToMILPBridge implements the following reformulation:

• $(n, x) \in \textsf{CountDistinct}(1+d)$ into a mixed-integer linear program.

Reformulation

The reformulation is non-trivial, and it depends on the finite domain of each variable $x_i$, which we as define $S_i = \{l_i,\ldots,u_i\}$.

First, we introduce new binary variables $z_{ij}$, which are $1$ if variable $x_i$ takes the value $j$ in the optimal solution and $0$ otherwise:

\begin{aligned} z_{ij} \in \{0, 1\} & \;\; \forall i \in 1\ldots d, j \in S_i \\ x_i - \sum\limits_{j\in S_i} j \cdot z_{ij} = 0 & \;\; \forall i \in 1\ldots d \\ \sum\limits_{j\in S_i} z_{ij} = 1 & \;\; \forall i \in 1\ldots d \\ \end{aligned}

Then, we introduce new binary variables $y_j$, which are $1$ if a variable takes the value $j$ in the optimal solution and $0$ otherwise.

\begin{aligned} y_{j} \in \{0, 1\} & \;\; \forall j \in \bigcup_{i=1,\ldots,d} S_i \\ y_j \le \sum\limits_{i \in 1\ldots d: j \in S_i} z_{ij} \le M y_j & \;\; \forall j \in \bigcup_{i=1,\ldots,d} S_i\\ \end{aligned}

Finally, $n$ is constrained to be the number of $y_j$ elements that are non-zero:

$$$n - \sum\limits_{j \in \bigcup_{i=1,\ldots,d} S_i} y_{j} = 0$$$

Formulation (special case)

In the special case that the constraint is [2, x, y] in CountDistinct(3), then the constraint is equivalent to [x, y] in AllDifferent(2), which is equivalent to x != y.

$$$(x - y <= -1) \vee (y - x <= -1)$$$

which is equivalent to (for suitable M):

\begin{aligned} z \in \{0, 1\} \\ x - y - M * z <= -1 \\ y - x - M * (1 - z) <= -1 \end{aligned}

Source node

CountDistinctToMILPBridge supports:

where F is MOI.VectorOfVariables or MOI.VectorAffineFunction{T}.

Target nodes

CountDistinctToMILPBridge creates:

source
MathOptInterface.Bridges.Constraint.CountGreaterThanToMILPBridgeType
CountGreaterThanToMILPBridge{T,F} <: Bridges.Constraint.AbstractBridge

CountGreaterThanToMILPBridge implements the following reformulation:

• $(c, y, x) \in CountGreaterThan()$ into a mixed-integer linear program.

Source node

CountGreaterThanToMILPBridge supports:

Target nodes

CountGreaterThanToMILPBridge creates:

source
MathOptInterface.Bridges.Constraint.FunctionConversionBridgeType
FunctionConversionBridge{T,F,G,S} <: AbstractFunctionConversionBridge{G,S}

FunctionConversionBridge implements the following reformulations:

• $g(x) \in S$ into $f(x) \in S$

for these pairs of functions:

Source node

FunctionConversionBridge supports:

• G in S

Target nodes

FunctionConversionBridge creates:

• F in S
source
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 not 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:

source
MathOptInterface.Bridges.Constraint.GeoMeanToPowerBridgeType
GeoMeanToPowerBridge{T,F} <: Bridges.Constraint.AbstractBridge

GeoMeanToPowerBridge implements the following reformulation:

• $(y, x...) \in GeometricMeanCone(1+d)$ into $(x_1, t, y) \in PowerCone(1/d)$ and $(t, x_2, ..., x_d) in GeometricMeanCone(d)$, which is then recursively expanded into more PowerCone constraints.

Source node

GeoMeanToPowerBridge supports:

Target nodes

GeoMeanToPowerBridge creates:

source
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.

source
MathOptInterface.Bridges.Constraint.GreaterToIntervalBridgeType
GreaterToIntervalBridge{T,F} <: Bridges.Constraint.AbstractBridge

GreaterToIntervalBridge implements the following reformulations:

• $f(x) \ge l$ into $f(x) \in [l, \infty)$

Source node

GreaterToIntervalBridge supports:

Target nodes

GreaterToIntervalBridge creates:

source
MathOptInterface.Bridges.Constraint.HermitianToSymmetricPSDBridgeType
HermitianToSymmetricPSDBridge{T,F,G} <: Bridges.Constraint.AbstractBridge

HermitianToSymmetricPSDBridge implements the following reformulation:

• Hermitian positive semidefinite n x n complex matrix to a symmetric positive semidefinite 2n x 2n real matrix.

Source node

HermitianToSymmetricPSDBridge supports:

Target node

HermitianToSymmetricPSDBridge creates:

Reformulation

The reformulation is best described by example.

The Hermitian matrix:

$$$\begin{bmatrix} x_{11} & x_{12} + y_{12}im & x_{13} + y_{13}im\\ x_{12} - y_{12}im & x_{22} & x_{23} + y_{23}im\\ x_{13} - y_{13}im & x_{23} - y_{23}im & x_{33} \end{bmatrix}$$$

is positive semidefinite if and only if the symmetric matrix:

$$$\begin{bmatrix} x_{11} & x_{12} & x_{13} & 0 & y_{12} & y_{13} \\ & x_{22} & x_{23} & -y_{12} & 0 & y_{23} \\ & & x_{33} & -y_{13} & -y_{23} & 0 \\ & & & x_{11} & x_{12} & x_{13} \\ & & & & x_{22} & x_{23} \\ & & & & & x_{33} \end{bmatrix}$$$

is positive semidefinite.

The bridge achieves this reformulation by constraining the above matrix to belong to the MOI.PositiveSemidefiniteConeTriangle(6).

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

IndicatorActiveOnFalseBridge implements the following reformulation:

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

Source node

IndicatorActiveOnFalseBridge supports:

Target nodes

IndicatorActiveOnFalseBridge creates:

source
MathOptInterface.Bridges.Constraint.IndicatorGreaterToLessThanBridgeType
IndicatorGreaterToLessThanBridge{T,A} <: Bridges.Constraint.AbstractBridge

IndicatorGreaterToLessThanBridge implements the following reformulation:

• $z \implies {f(x) \ge l}$ into $z \implies {-f(x) \le -l}$

Source node

IndicatorGreaterToLessThanBridge supports:

Target nodes

IndicatorGreaterToLessThanBridge creates:

source
MathOptInterface.Bridges.Constraint.IndicatorLessToGreaterThanBridgeType
IndicatorLessToGreaterThanBridge{T,A} <: Bridges.Constraint.AbstractBridge

IndicatorLessToGreaterThanBridge implements the following reformulations:

• $z \implies {f(x) \le u}$ into $z \implies {-f(x) \ge -u}$

Source node

IndicatorLessToGreaterThanBridge supports:

Target nodes

IndicatorLessToGreaterThanBridge creates:

source
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:

source
MathOptInterface.Bridges.Constraint.IndicatorSetMapBridgeType
IndicatorSetMapBridge{T,A,S1,S2} <: Bridges.Constraint.AbstractBridge

IndicatorSetMapBridge implements the following reformulations:

• $z \implies {f(x) \ge l}$ into $z \implies {-f(x) \le -l}$
• $z \implies {f(x) \le u}$ into $z \implies {-f(x) \ge -u}$

Source node

IndicatorSetMapBridge supports:

Target nodes

IndicatorSetMapBridge creates:

source
MathOptInterface.Bridges.Constraint.IndicatorToMILPBridgeType
IndicatorToMILPBridge{T,F,A,S} <: Bridges.Constraint.AbstractBridge

IndicatorToMILPBridge implements the following reformulation:

• $x \in \textsf{Indicator}(s)$ into a mixed-integer linear program.

Source node

IndicatorToMILPBridge supports:

where F is MOI.VectorOfVariables or MOI.VectorAffineFunction{T}.

Target nodes

IndicatorToMILPBridge creates:

source
MathOptInterface.Bridges.Constraint.IntegerToZeroOneBridgeType
IntegerToZeroOneBridge{T} <: Bridges.Constraint.AbstractBridge

IntegerToZeroOneBridge implements the following reformulation:

• $x \in \mathbf{Z}$ into $y_i \in \{0, 1\}$, $x == lb + \sum 2^{i-1} y_i$.

Source node

IntegerToZeroOneBridge supports:

Target nodes

IntegerToZeroOneBridge creates:

Developer note

This bridge is implemented as a constraint bridge instead of a variable bridge because we don't want to substitute the linear combination of y for every instance of x. Doing so would be expensive and greatly reduce the sparsity of the constraints.

source
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\left(\frac{Δ_{ii}}{u}\right) & \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\quad \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.

source
MathOptInterface.Bridges.Constraint.MultiSetMapBridgeType
abstract type MultiSetMapBridge{T,S1,G} <: AbstractBridge end

Same as SetMapBridge but the output constraint type does not only depend on the input constraint type.

When subtyping MultiSetMapBridge, added_constraint_types and supports should additionally be implemented by the bridge.

For example, if a bridge BridgeType may create either a constraint of type F2-in-S2 or F3-in-S3, these methods should be implemented as follows:

function MOI.Bridges.added_constraint_types(
::Type{<:BridgeType{T,F2,F3}},
) where {T,F2,F3}
return Tuple{Type,Type}[(F2, S2), (F3, S3)]
end

function MOI.supports(
model::MOI.ModelLike,
attr::Union{MOI.ConstraintPrimalStart,MOI.ConstraintDualStart},
::Type{<:BridgeType{T,F2,F3}},
) where {T,F2,F3}
return MOI.supports(model, attr, MOI.ConstraintIndex{F2,S2}) ||
MOI.supports(model, attr, MOI.ConstraintIndex{F3,S3})
end
source
MathOptInterface.Bridges.Constraint.NonnegToNonposBridgeType
NonnegToNonposBridge{T,F,G} <: Bridges.Constraint.AbstractBridge

NonnegToNonposBridge implements the following reformulation:

• $f(x) \in \mathbb{R}_+$ into $-f(x) \in \mathbb{R}_-$

Source node

NonnegToNonposBridge supports:

Target nodes

NonnegToNonposBridge creates:

source
MathOptInterface.Bridges.Constraint.NonposToNonnegBridgeType
NonposToNonnegBridge{T,F,G} <: Bridges.Constraint.AbstractBridge

NonposToNonnegBridge implements the following reformulation:

• $f(x) \in \mathbb{R}_-$ into $-f(x) \in \mathbb{R}_+$

Source node

NonposToNonnegBridge supports:

Target nodes

NonposToNonnegBridge creates:

source
MathOptInterface.Bridges.Constraint.NormInfinityBridgeType
NormInfinityBridge{T,F,G} <: Bridges.Constraint.AbstractBridge

NormInfinityBridge implements the following reformulation:

• $|x|_\infty \le t$ into $[t - x_i, t + x_i] \in \mathbb{R}_+$.

Source node

NormInfinityBridge supports:

Target nodes

NormInfinityBridge creates:

source
MathOptInterface.Bridges.Constraint.NormInfinityConeToNormConeBridgeType
NormInfinityConeToNormConeBridge{T,F} <: Bridges.Constraint.AbstractBridge

NormInfinityConeToNormConeBridge implements the following reformulations:

• $(t, x) in NormInfinityCone(d)$ into $(t, x) in NormCone(Inf, d)$

Source node

NormInfinityConeToNormConeBridge supports:

Target nodes

NormInfinityConeToNormConeBridge creates:

source
MathOptInterface.Bridges.Constraint.NormNuclearBridgeType
NormNuclearBridge{T,F,G,H} <: Bridges.Constraint.AbstractBridge

NormNuclearBridge implements the following reformulation:

• $t \ge \sum_i \sigma_i (X)$ into $\left[\begin{array}{c c}U & X^\top \\ X & V\end{array}\right] \succeq 0$ and $2t \ge tr(U) + tr(V)$.

Source node

NormNuclearBridge supports:

Target nodes

NormNuclearBridge creates:

source
MathOptInterface.Bridges.Constraint.NormOneBridgeType
NormOneBridge{T,F,G} <: Bridges.Constraint.AbstractBridge

NormOneBridge implements the following reformulation:

• $\sum |x_i| \le t$ into $[t - \sum y_i, y_i - x_i, y_i + x_i] \in \mathbb{R}_+$.

Source node

NormOneBridge supports:

Target nodes

NormOneBridge creates:

source
MathOptInterface.Bridges.Constraint.NormOneConeToNormConeBridgeType
NormOneConeToNormConeBridge{T,F} <: Bridges.Constraint.AbstractBridge

NormOneConeToNormConeBridge implements the following reformulations:

• $(t, x) in NormOneCone(d)$ into $(t, x) in NormCone(1, d)$

Source node

NormOneConeToNormConeBridge supports:

Target nodes

NormOneConeToNormConeBridge creates:

source
MathOptInterface.Bridges.Constraint.NormSpectralBridgeType
NormSpectralBridge{T,F,G} <: Bridges.Constraint.AbstractBridge

NormSpectralBridge implements the following reformulation:

• $t \ge \sigma_1(X)$ into $\left[\begin{array}{c c}t\mathbf{I} & X^\top \\ X & t \mathbf{I}\end{array}\right] \succeq 0$

Source node

NormSpectralBridge supports:

Target nodes

NormSpectralBridge creates:

source
MathOptInterface.Bridges.Constraint.NormToPowerBridgeType
NormToPowerBridge{T,F} <: Bridges.Constraint.AbstractBridge

NormToPowerBridge implements the following reformulation:

• $(t, x) \in NormCone(p, 1+d)$ into $(r_i, t, x_i) \in PowerCone(1 / p)$ for all $i$, and $\sum\limits_i r_i == t$.

For details, see Alizadeh, F., and Goldfarb, D. (2001). "Second-order cone programming." Mathematical Programming, Series B, 95:3-51.

Source node

NormToPowerBridge supports:

Target nodes

NormToPowerBridge creates:

source
MathOptInterface.Bridges.Constraint.NumberConversionBridgeType
NumberConversionBridge{T,F1,S1,F2,S2} <: Bridges.Constraint.AbstractBridge

NumberConversionBridge implements the following reformulation:

• $f1(x) \in S1$ to $f2(x) \in S2$

where f and S are the same functional form, but differ in their coefficient type.

Source node

NumberConversionBridge supports:

• F1 in S1

Target node

NumberConversionBridge creates:

• F2 in S2
source
MathOptInterface.Bridges.Constraint.QuadtoSOCBridgeType
QuadtoSOCBridge{T} <: Bridges.Constraint.AbstractBridge

QuadtoSOCBridge converts quadratic inequalities

$$$\frac{1}{2}x^T Q x + a^T x \le ub$$$

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

This is because, if Q is positive definite, 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 + ub)$$$

Therefore, QuadtoSOCBridge implements the following reformulations:

• $\frac{1}{2}x^T Q x + a^T x \le ub$ into $(1, -a^T x + ub, Ux) \in RotatedSecondOrderCone$ where $Q = U^T U$
• $\frac{1}{2}x^T Q x + a^T x \ge lb$ into $(1, a^T x - lb, Ux) \in RotatedSecondOrderCone$ where $-Q = U^T U$

Source node

QuadtoSOCBridge supports:

Target nodes

RelativeEntropyBridge creates:

Errors

This bridge errors if Q is not positive definite.

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

RSOCtoNonConvexQuadBridge implements the following reformulations:

• $||x||_2^2 \le 2tu$ into $\sum x^2 - 2tu \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:

source
MathOptInterface.Bridges.Constraint.RSOCtoPSDBridgeType
RSOCtoPSDBridge{T,F,G} <: Bridges.Constraint.AbstractBridge

RSOCtoPSDBridge implements the following reformulation:

• $||x||_2^2 \le 2t\cdot u$ into $\left[\begin{array}{c c}t & x^\top \\ x & 2tu \mathbf{I}\end{array}\right]\succeq 0$

Source node

RSOCtoPSDBridge supports:

Target nodes

RSOCtoPSDBridge creates:

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

RSOCtoSOCBridge implements the following reformulation:

• $||x||_2^2 \le 2tu$ into $||\frac{t - u}{\sqrt 2}, x||_2 \le \frac{t + u}{\sqrt 2}$

Source node

RSOCtoSOCBridge supports:

Target node

RSOCtoSOCBridge creates:

source
MathOptInterface.Bridges.Constraint.ReifiedAllDifferentToCountDistinctBridgeType
ReifiedAllDifferentToCountDistinctBridge{T,F} <:
Bridges.Constraint.AbstractBridge

ReifiedAllDifferentToCountDistinctBridge implements the following reformulations:

• $r \iff x \in \textsf{AllDifferent}(d)$ to $r \iff (n, x) \in \textsf{CountDistinct}(1+d)$ and $n = d$
• $r \iff f(x) \in \textsf{AllDifferent}(d)$ to $r \iff (d, f(x)) \in \textsf{CountDistinct}(1+d)$

Source node

ReifiedAllDifferentToCountDistinctBridge supports:

where F is MOI.VectorOfVariables or MOI.VectorAffineFunction{T}.

Target nodes

ReifiedAllDifferentToCountDistinctBridge creates:

source
MathOptInterface.Bridges.Constraint.ReifiedCountDistinctToMILPBridgeType
ReifiedCountDistinctToMILPBridge{T,F} <: Bridges.Constraint.AbstractBridge

ReifiedCountDistinctToMILPBridge implements the following reformulation:

• $r \iff (n, x) \in \textsf{CountDistinct}(1+d)$ into a mixed-integer linear program.

Reformulation

The reformulation is non-trivial, and it depends on the finite domain of each variable $x_i$, which we as define $S_i = \{l_i,\ldots,u_i\}$.

First, we introduce new binary variables $z_{ij}$, which are $1$ if variable $x_i$ takes the value $j$ in the optimal solution and $0$ otherwise:

\begin{aligned} z_{ij} \in \{0, 1\} & \;\; \forall i \in 1\ldots d, j \in S_i \\ x_i - \sum\limits_{j\in S_i} j \cdot z_{ij} = 0 & \;\; \forall i \in 1\ldots d \\ \sum\limits_{j\in S_i} z_{ij} = 1 & \;\; \forall i \in 1\ldots d \\ \end{aligned}

Then, we introduce new binary variables $y_j$, which are $1$ if a variable takes the value $j$ in the optimal solution and $0$ otherwise.

\begin{aligned} y_{j} \in \{0, 1\} & \;\; \forall j \in \bigcup_{i=1,\ldots,d} S_i \\ y_j \le \sum\limits_{i \in 1\ldots d: j \in S_i} z_{ij} \le M y_j & \;\; \forall j \in \bigcup_{i=1,\ldots,d} S_i\\ \end{aligned}

Finally, $n$ is constrained to be the number of $y_j$ elements that are non-zero, with some slack:

$$$n - \sum\limits_{j \in \bigcup_{i=1,\ldots,d} S_i} y_{j} = \delta^+ - \delta^-$$$

And then the slack is constrained to respect the reif variable $r$:

\begin{aligned} d_1 \le \delta^+ \le M d_1 \\ d_2 \le \delta^- \le M d_s \\ d_1 + d_2 + r = 1 \\ d_1, d_2 \in \{0, 1\} \end{aligned}

Source node

ReifiedCountDistinctToMILPBridge supports:

where F is MOI.VectorOfVariables or MOI.VectorAffineFunction{T}.

Target nodes

ReifiedCountDistinctToMILPBridge creates:

source
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$, $u \ge \sum_{i=1}^n y_i$, and $(-y_i, w_i, v_i) \in ExponentialCone$.

Source node

RelativeEntropyBridge supports:

Target nodes

RelativeEntropyBridge creates:

source
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.

source
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:

source
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]\succeq 0$
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:

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

SOCtoRSOCBridge implements the following reformulation:

• $||x||_2 \le t$ into $(t+x_1)(t-x_1)\ge ||(x_2\ldots,x_N)||_2^2$

Assumptions

• SOCtoRSOCBridge assumes that the length of x is at least one.

Source node

SOCtoRSOCBridge supports:

Target node

SOCtoRSOCBridge creates:

source
MathOptInterface.Bridges.Constraint.SOS1ToMILPBridgeType
SOS1ToMILPBridge{T,F} <: Bridges.Constraint.AbstractBridge

SOS1ToMILPBridge implements the following reformulation:

• $x \in \textsf{SOS1}(d)$ into a mixed-integer linear program.

Source node

SOS1ToMILPBridge supports:

where F is MOI.VectorOfVariables or MOI.VectorAffineFunction{T}.

Target nodes

SOS1ToMILPBridge creates:

source
MathOptInterface.Bridges.Constraint.SOS2ToMILPBridgeType
SOS2ToMILPBridge{T,F} <: Bridges.Constraint.AbstractBridge

SOS2ToMILPBridge implements the following reformulation:

• $x \in \textsf{SOS2}(d)$ into a mixed-integer linear program.

Source node

SOS2ToMILPBridge supports:

where F is MOI.VectorOfVariables or MOI.VectorAffineFunction{T}.

Target nodes

SOS2ToMILPBridge creates:

source
MathOptInterface.Bridges.Constraint.ScalarFunctionizeBridgeType
ScalarFunctionizeBridge{T,S} = FunctionConversionBridge{T,MOI.ScalarAffineFunction{T},MOI.VariableIndex,S}

ScalarFunctionizeBridge implements the following reformulations:

• $x \in S$ into $1x + 0 \in S$

Source node

ScalarFunctionizeBridge supports:

Target nodes

ScalarFunctionizeBridge creates:

source
MathOptInterface.Bridges.Constraint.ScalarSlackBridgeType
ScalarSlackBridge{T,F,S} <: Bridges.Constraint.AbstractBridge

ScalarSlackBridge implements the following reformulation:

• $f(x) \in S$ into $f(x) - y == 0$ and $y \in S$

Source node

ScalarSlackBridge supports:

Target nodes

ScalarSlackBridge creates:

source
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:

source
MathOptInterface.Bridges.Constraint.SecondOrderConeToNormConeBridgeType
SecondOrderConeToNormConeBridge{T,F} <: Bridges.Constraint.AbstractBridge

SecondOrderConeToNormConeBridge implements the following reformulations:

• $(t, x) in SecondOrderCone(d)$ into $(t, x) in NormCone(2, d)$

Source node

SecondOrderConeToNormConeBridge supports:

Target nodes

SecondOrderConeToNormConeBridge creates:

source
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 u \\ x \geq z l \\ z \in \{0, 1\} \end{aligned}
• $x \in \{0\} \cup \{l, \ldots, u\}$ into\begin{aligned} x \leq z u \\ x \geq z l \\ z \in \{0, 1\} \\ x \in \mathbb{Z} \end{aligned}

Source node

SemiToBinaryBridge supports:

Target nodes

SemiToBinaryBridge creates:

source
MathOptInterface.Bridges.Constraint.SetDotInverseScalingBridgeType
SetDotInverseScalingBridge{T,S,F,G} <: Bridges.Constraint.AbstractBridge

SetDotInverseScalingBridge implements the reformulation from constraints in the MOI.Scaled{S} to constraints in the S.

Source node

SetDotInverseScalingBridge supports:

Target node

SetDotInverseScalingBridge creates:

• F in S
source
MathOptInterface.Bridges.Constraint.SetDotScalingBridgeType
SetDotScalingBridge{T,S,F,G} <: Bridges.Constraint.AbstractBridge

SetDotScalingBridge implements the reformulation from constraints in S to constraints in MOI.Scaled{S}.

Source node

SetDotScalingBridge supports:

• G in S

Target node

SetDotScalingBridge creates:

source
MathOptInterface.Bridges.Constraint.SetMapBridgeType
abstract type SetMapBridge{T,S2,S1,F,G} <: MultiSetMapBridge{T,S1,G} end

Consider two type of sets, S1 and S2, and a linear mapping A such that the image of a set of type S1 under A is a set of type S2.

A SetMapBridge{T,S2,S1,F,G} is a bridge that maps G-in-S1 constraints into F-in-S2 by mapping the function through A.

The linear map A is described by;

Implementing a method for these two functions is sufficient to bridge constraints. However, in order for the getters and setters of attributes such as dual solutions and starting values to work as well, a method for the following functions must be implemented:

See the docstrings of each function to see which feature would be missing if it was not implemented for a given bridge.

source
MathOptInterface.Bridges.Constraint.SplitComplexEqualToBridgeType
SplitComplexEqualToBridge{T,F,G} <: Bridges.Constraint.AbstractBridge

SplitComplexEqualToBridge implements the following reformulation:

• $f(x) + g(x) * im = a + b * im$ into $f(x) = a$ and $g(x) = b$

Source node

SplitComplexEqualToBridge supports:

where G is a function with Complex coefficients.

Target nodes

SplitComplexEqualToBridge creates:

where F is the type of the real/imaginary part of G.

source
MathOptInterface.Bridges.Constraint.SplitComplexZerosBridgeType
SplitComplexZerosBridge{T,F,G} <: Bridges.Constraint.AbstractBridge

SplitComplexZerosBridge implements the following reformulation:

• $f(x) \in \{0\}^n$ into $\text{Re}(f(x)) \in \{0\}^n$ and $\text{Im}(f(x)) \in \{0\}^n$

Source node

SplitComplexZerosBridge supports:

where G is a function with Complex coefficients.

Target nodes

SplitComplexZerosBridge creates:

where F is the type of the real/imaginary part of G.

source
MathOptInterface.Bridges.Constraint.SplitHyperRectangleBridgeType
SplitHyperRectangleBridge{T,G,F} <: Bridges.Constraint.AbstractBridge

SplitHyperRectangleBridge implements the following reformulation:

• $f(x) \in \textsf{HyperRectangle}(l, u)$ to $[f(x) - l; u - f(x)] \in \mathbb{R}_+$.

Source node

SplitHyperRectangleBridge supports:

Target nodes

SplitHyperRectangleBridge creates:

source
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.

source
MathOptInterface.Bridges.Constraint.SquareBridgeType
SquareBridge{T,F,G,TT,ST} <: Bridges.Constraint.AbstractBridge

SquareBridge implements the following reformulations:

• $(t, u, X) \in LogDetConeSquare$ into $(t, u, Y) in LogDetConeTriangle$
• $(t, X) \in RootDetConeSquare$ into $(t, Y) in RootDetConeTriangle$
• $X \in AbstractSymmetricMatrixSetSquare$ into $Y in AbstractSymmetricMatrixSetTriangle$

where $Y$ is the upper triangluar component of $X$.

In addition, constraints are added as necessary to constrain the matrix $X$ to be symmetric. For example, 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}$$$

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) $3 - x == 2 + x$. Note that no symmetrization constraint needs to be added between the off-diagonal entries (1, 2) and (2, 1) or between (1, 3) and (3, 1) because the expressions are the same.

Source node

SquareBridge supports:

• F in ST

Target nodes

SquareBridge creates:

• G in TT
source
MathOptInterface.Bridges.Constraint.TableToMILPBridgeType
TableToMILPBridge{T,F} <: Bridges.Constraint.AbstractBridge

TableToMILPBridge implements the following reformulation:

• $x \in Table(t)$ into\begin{aligned} z_{j} \in \{0, 1\} & \quad \forall i, j \\ \sum\limits_{j=1}^n z_{j} = 1 \\ \sum\limits_{j=1}^n t_{ij} z_{j} = x_i & \quad \forall i \end{aligned}

Source node

TableToMILPBridge supports:

Target nodes

TableToMILPBridge creates:

source
MathOptInterface.Bridges.Constraint.ToScalarNonlinearBridgeType
ToScalarNonlinearBridge{T,G,S} <: AbstractFunctionConversionBridge{G,S}

ToScalarNonlinearBridge implements the following reformulation:

• $g(x) \in S$ into $f(x) \in S$

where g is an abstract scalar function and f is a MOI.ScalarNonlinearFunction.

Source node

ToScalarNonlinearBridge supports:

• G<:AbstractScalarFunction in S

Target nodes

ToScalarNonlinearBridge creates:

source
MathOptInterface.Bridges.Constraint.ToScalarQuadraticBridgeType
ToScalarQuadraticBridge{T,G,S} <: AbstractFunctionConversionBridge{G,S}

ToScalarQuadraticBridge implements the following reformulation:

• $g(x) \in S$ into $f(x) \in S$

where g is an abstract scalar function and f is a MOI.ScalarQuadraticFunction.

Source node

ToScalarQuadraticBridge supports:

• G<:AbstractScalarFunction in S

Target nodes

ToScalarQuadraticBridge creates:

source
MathOptInterface.Bridges.Constraint.ToVectorQuadraticBridgeType
ToVectorQuadraticBridge{T,G,S} <: AbstractFunctionConversionBridge{G,S}

ToVectorQuadraticBridge implements the following reformulation:

• $g(x) \in S$ into $f(x) \in S$

where g is an abstract vector function and f is a MOI.VectorQuadraticFunction.

Source node

ToVectorQuadraticBridge supports:

• G<:AbstractVectorFunction in S

Target nodes

ToVectorQuadraticBridge creates:

source
MathOptInterface.Bridges.Constraint.VectorFunctionizeBridgeType
VectorFunctionizeBridge{T,S} = FunctionConversionBridge{T,MOI.VectorAffineFunction{T},S}

VectorFunctionizeBridge implements the following reformulations:

• $x \in S$ into $Ix + 0 \in S$

Source node

VectorFunctionizeBridge supports:

Target nodes

VectorFunctionizeBridge creates:

source
MathOptInterface.Bridges.Constraint.VectorSlackBridgeType
VectorSlackBridge{T,F,S} <: Bridges.Constraint.AbstractBridge

VectorSlackBridge implements the following reformulation:

• $f(x) \in S$ into $f(x) - y \in \{0\}$ and $y \in S$

Source node

VectorSlackBridge supports:

Target nodes

VectorSlackBridge creates:

source
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:

source
MathOptInterface.Bridges.Constraint.ZeroOneBridgeType
ZeroOneBridge{T} <: Bridges.Constraint.AbstractBridge

ZeroOneBridge implements the following reformulation:

• $x \in \{0, 1\}$ into $x \in \mathbb{Z}$, $1x \in [0, 1]$.
Note

ZeroOneBridge adds a linear constraint instead of adding variable bounds to avoid conflicting with bounds set by the user.

Source node

ZeroOneBridge supports:

Target nodes

ZeroOneBridge creates:

source

## Objective bridges

These bridges are subtypes of Bridges.Objective.AbstractBridge.

MathOptInterface.Bridges.Objective.FunctionConversionBridgeType
FunctionConversionBridge{T,F,G} <: AbstractBridge

FunctionConversionBridge implements the following reformulations:

• $\min \{g(x)\}$ into $\min\{f(x)\}$
• $\max \{g(x)\}$ into $\max\{f(x)\}$

for these pairs of functions:

Source node

FunctionConversionBridge supports:

Target nodes

FunctionConversionBridge creates:

source
MathOptInterface.Bridges.Objective.FunctionizeBridgeType
FunctionizeBridge{T,G} <: FunctionConversionBridge{T,MOI.ScalarAffineFunction{T},G}

FunctionizeBridge implements the following reformulations:

• $\min \{x\}$ into $\min\{1x + 0\}$
• $\max \{x\}$ into $\max\{1x + 0\}$

where T is the coefficient type of 1 and 0.

Source node

FunctionizeBridge supports:

Target nodes

FunctionizeBridge creates:

source
MathOptInterface.Bridges.Objective.QuadratizeBridgeType
QuadratizeBridge{T,G} <: FunctionConversionBridge{T,MOI.ScalarQuadraticFunction{T},G}

QuadratizeBridge implements the following reformulations:

• $\min \{a^\top x + b\}$ into $\min\{x^\top \mathbf{0} x + a^\top x + b\}$
• $\max \{a^\top x + b\}$ into $\max\{x^\top \mathbf{0} x + a^\top x + b\}$

where T is the coefficient type of 0.

Source node

QuadratizeBridge supports:

Target nodes

QuadratizeBridge creates:

source
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.

source
MathOptInterface.Bridges.Objective.VectorFunctionizeBridgeType
VectorFunctionizeBridge{T,G} <: FunctionConversionBridge{T,MOI.VectorAffineFunction{T},G}

VectorFunctionizeBridge implements the following reformulations:

• $\min \{x\}$ into $\min\{1x + 0\}$
• $\max \{x\}$ into $\max\{1x + 0\}$

where T is the coefficient type of 1 and 0.

Source node

VectorFunctionizeBridge supports:

Target nodes

VectorFunctionizeBridge creates:

source
MathOptInterface.Bridges.Objective.VectorSlackBridgeType
VectorSlackBridge{T,F,G}

VectorSlackBridge implements the following reformulations:

• $\min\{f(x)\}$ into $\min\{y\;|\; y - f(x) \in \mathbb{R}_+ \}$
• $\max\{f(x)\}$ into $\max\{y\;|\; f(x) - y \in \mathbb{R}_+ \}$

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

VectorSlackBridge supports:

Target nodes

VectorSlackBridge 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.

source

## Variable bridges

These bridges are subtypes of Bridges.Variable.AbstractBridge.

MathOptInterface.Bridges.Variable.FreeBridgeType
FreeBridge{T} <: Bridges.Variable.AbstractBridge

FreeBridge implements the following reformulation:

• $x \in \mathbb{R}$ into $y, z \ge 0$ with the substitution rule $x = y - z$,

where T is the coefficient type of y - z.

Source node

FreeBridge supports:

Target nodes

FreeBridge creates:

source
MathOptInterface.Bridges.Variable.HermitianToSymmetricPSDBridgeType
HermitianToSymmetricPSDBridge{T} <: Bridges.Variable.AbstractBridge

HermitianToSymmetricPSDBridge implements the following reformulation:

• Hermitian positive semidefinite n x n complex matrix to a symmetric positive semidefinite 2n x 2n real matrix satisfying equality constraints described below.

Source node

HermitianToSymmetricPSDBridge supports:

Target node

HermitianToSymmetricPSDBridge creates:

Reformulation

The reformulation is best described by example.

The Hermitian matrix:

$$$\begin{bmatrix} x_{11} & x_{12} + y_{12}im & x_{13} + y_{13}im\\ x_{12} - y_{12}im & x_{22} & x_{23} + y_{23}im\\ x_{13} - y_{13}im & x_{23} - y_{23}im & x_{33} \end{bmatrix}$$$

is positive semidefinite if and only if the symmetric matrix:

$$$\begin{bmatrix} x_{11} & x_{12} & x_{13} & 0 & y_{12} & y_{13} \\ & x_{22} & x_{23} & -y_{12} & 0 & y_{23} \\ & & x_{33} & -y_{13} & -y_{23} & 0 \\ & & & x_{11} & x_{12} & x_{13} \\ & & & & x_{22} & x_{23} \\ & & & & & x_{33} \end{bmatrix}$$$

is positive semidefinite.

The bridge achieves this reformulation by adding a new set of variables in MOI.PositiveSemidefiniteConeTriangle(6), and then adding three groups of equality constraints to:

• constrain the two x blocks to be equal
• force the diagonal of the y blocks to be 0
• force the lower triangular of the y block to be the negative of the upper triangle.
source
MathOptInterface.Bridges.Variable.NonposToNonnegBridgeType
NonposToNonnegBridge{T} <: Bridges.Variable.AbstractBridge

NonposToNonnegBridge implements the following reformulation:

• $x \in \mathbb{R}_-$ into $y \in \mathbb{R}_+$ with the substitution rule $x = -y$,

where T is the coefficient type of -y.

Source node

NonposToNonnegBridge supports:

Target nodes

NonposToNonnegBridge creates:

source
MathOptInterface.Bridges.Variable.ParameterToEqualToBridgeType
ParameterToEqualToBridge{T} <: Bridges.Variable.AbstractBridge

ParameterToEqualToBridge implements the following reformulation:

• $x \in Parameter(v)$ into $x == v$

Source node

ParameterToEqualToBridge supports:

Target nodes

ParameterToEqualToBridge creates:

source
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 ensure 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:

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

RSOCtoSOCBridge implements the following reformulation:

• $||x||_2^2 \le 2tu$ into $||v||_2 \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:

source
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:

source
MathOptInterface.Bridges.Variable.SetMapBridgeType
abstract type SetMapBridge{T,S1,S2} <: AbstractBridge end

Consider two type of sets, S1 and S2, and a linear mapping A such that the image of a set of type S1 under A is a set of type S2.

A SetMapBridge{T,S1,S2} is a bridge that substitutes constrained variables in S2 into the image through A of constrained variables in S1.

The linear map A is described by:

Implementing a method for these two functions is sufficient to bridge constrained variables. However, in order for the getters and setters of attributes such as dual solutions and starting values to work as well, a method for the following functions must be implemented:

See the docstrings of each function to see which feature would be missing if it was not implemented for a given bridge.

source
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:

source
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.

source