# Bridges

MathOptInterface.Bridges.AbstractBridgeType
AbstractBridge

Represents a bridged constraint or variable in a MathOptInterface.Bridges.AbstractBridgeOptimizer. It contains the indices of the variables and constraints that it has created in the model. These can be obtained using MathOptInterface.NumberOfVariables, MathOptInterface.ListOfVariableIndices, MathOptInterface.NumberOfConstraints and MathOptInterface.ListOfConstraintIndices using MathOptInterface.get with the bridge in place of the MathOptInterface.ModelLike. Attributes of the bridged model such as MathOptInterface.ConstraintDual and MathOptInterface.ConstraintPrimal, can be obtained using MathOptInterface.get with the bridge in place of the constraint index. These calls are used by the MathOptInterface.Bridges.AbstractBridgeOptimizer to communicate with the bridge so they should be implemented by the bridge.

MathOptInterface.Bridges.AbstractBridgeOptimizerType
AbstractBridgeOptimizer

A bridge optimizer applies given constraint bridges to a given optimizer thus extending the types of supported constraints. The attributes of the inner optimizer are automatically transformed to make the bridges transparent, e.g. the variables and constraints created by the bridges are hidden.

By convention, the inner optimizer should be stored in a model field and the dictionary mapping constraint indices to bridges should be stored in a bridges field. If a bridge optimizer deviates from these conventions, it should implement the functions MOI.optimize! and bridge respectively.

MathOptInterface.Bridges.LazyBridgeOptimizerType
LazyBridgeOptimizer{OT<:MOI.ModelLike} <: AbstractBridgeOptimizer

The LazyBridgeOptimizer combines several bridges, which are added using the add_bridge function.

Whenever a constraint is added, it only attempts to bridge it if it is not supported by the internal model (hence its name Lazy).

When bridging a constraint, it selects the minimal number of bridges needed.

For example, if a constraint F-in-S can be bridged into a constraint F1-in-S1 (supported by the internal model) using bridge 1 or bridged into a constraint F2-in-S2 (unsupported by the internal model) using bridge 2 which can then be bridged into a constraint F3-in-S3 (supported by the internal model) using bridge 3, it will choose bridge 1 as it allows to bridge F-in-S using only one bridge instead of two if it uses bridge 2 and 3.

MathOptInterface.Bridges.has_bridgeFunction
has_bridge(b::LazyBridgeOptimizer, BT::Type{<:AbstractBridge})

Return a Bool indicating whether the bridges of type BT are used by b.

MathOptInterface.Bridges.full_bridge_optimizerFunction
full_bridge_optimizer(model::MOI.ModelLike, ::Type{T}) where {T}

Returns a LazyBridgeOptimizer bridging model for every bridge defined in this package (see below for the few exceptions) and for the coefficient type T in addition to the bridges in the list returned by MOI.get(model, MOI.Bridges.ListOfNonstandardBridges{T}()).

Note

The following bridges are not added by full_bridge_optimizer except if they are in the list returned by MOI.get(model, MOI.Bridges.ListOfNonstandardBridges{T}()) (see the docstrings of the corresponding bridge for the reason they are not added):

MathOptInterface.Bridges.ListOfNonstandardBridgesType
ListOfNonstandardBridges{T}() <: MOI.AbstractOptimizerAttribute

Any optimizer can be wrapped in a LazyBridgeOptimizer using full_bridge_optimizer. However, by default LazyBridgeOptimizer uses a limited set of bridges that are:

1. implemented in MOI.Bridges
2. generally applicable for all optimizers.

For some optimizers however, it is useful to add additional bridges, such as those that are implemented in external packages (e.g., within the solver package itself) or only apply in certain circumstances (e.g., Constraint.SOCtoNonConvexQuadBridge).

Such optimizers should implement the ListOfNonstandardBridges attribute to return a vector of bridge types that are added by full_bridge_optimizer in addition to the list of default bridges.

Note that optimizers implementing ListOfNonstandardBridges may require package-specific functions or sets to be used if the non-standard bridges are not added. Therefore, you are recommended to use model = MOI.instantiate(Package.Optimizer; with_bridge_type = T) instead of model = MOI.instantiate(Package.Optimizer). See MathOptInterface.instantiate.

Examples

An optimizer using a non-default bridge in MOI.Bridges

Solvers supporting MOI.ScalarQuadraticFunction can support MOI.SecondOrderCone and MOI.RotatedSecondOrderCone by defining:

return Type[
]
end

An optimizer defining an internal bridge

Suppose an optimizer can exploit specific structure of a constraint, e.g., it can exploit the structure of the matrix A in the linear system of equations A * x = b.

The optimizer can define the function:

struct MatrixAffineFunction{T} <: MOI.AbstractVectorFunction
A::SomeStructuredMatrixType{T}
b::Vector{T}
end

and then a bridge

struct MatrixAffineFunctionBridge{T} <: MOI.Constraint.AbstractBridge
# ...
end
# ...

from VectorAffineFunction{T} to the MatrixAffineFunction. Finally, it defines:

function MOI.get(::Optimizer{T}, ::ListOfNonstandardBridges{T}) where {T}
return Type[MatrixAffineFunctionBridge{T}]
end
MathOptInterface.Bridges.bridged_variable_functionFunction
bridged_variable_function(
b::AbstractBridgeOptimizer,
vi::MOI.VariableIndex,
)

Return a MOI.AbstractScalarFunction of variables of b.model that equals vi. That is, if the variable vi is bridged, it returns its expression in terms of the variables of b.model. Otherwise, it returns vi.

MathOptInterface.Bridges.unbridged_variable_functionFunction
unbridged_variable_function(
b::AbstractBridgeOptimizer,
vi::MOI.VariableIndex,
)

Return a MOI.AbstractScalarFunction of variables of b that equals vi. That is, if the variable vi is an internal variable of b.model created by a bridge but not visible to the user, it returns its expression in terms of the variables of bridged variables. Otherwise, it returns vi.

MathOptInterface.Bridges.Variable.unbridged_mapFunction

unbridged_map( bridge::MOI.Bridges.Variable.AbstractBridge, vi::MOI.VariableIndex, )

For a bridged variable in a scalar set, return a tuple of pairs mapping the variables created by the bridge to an affine expression in terms of the bridged variable vi.

unbridged_map(
bridge::MOI.Bridges.Variable.AbstractBridge,
vis::Vector{MOI.VariableIndex},
)

For a bridged variable in a vector set, return a tuple of pairs mapping the variables created by the bridge to an affine expression in terms of the bridged variable vis. If this method is not implemented, it falls back to calling the following method for every variable of vis.

unbridged_map(
bridge::MOI.Bridges.Variable.AbstractBridge,
vi::MOI.VariableIndex,
i::MOIB.IndexInVector,
)

For a bridged variable in a vector set, return a tuple of pairs mapping the variables created by the bridge to an affine expression in terms of the bridged variable vi corresponding to the ith variable of the vector.

If there is no way to recover the expression in terms of the bridged variable(s) vi(s), return nothing. See ZerosBridge for an example of bridge returning nothing.

## Constraint bridges

MathOptInterface.Bridges.Constraint.AbstractFunctionConversionBridgeType
abstract type AbstractFunctionConversionBridge{F, S} <: AbstractBridge end

Bridge a constraint G-in-S into a constraint F-in-S where F and G are equivalent representations of the same function. By convention, the transformed function is stored in the constraint field.

### SetMap bridges

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

Consider two type of sets S1, S2 and a linear mapping A 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 MathOptInterface.Bridges.map_set, MathOptInterface.Bridges.map_function. Implementing a method for these two functions is sufficient to bridge constrained variables. In order for the getters and setters of dual solutions, starting values, etc... to work as well a method for the following functions should be implemented as well: MathOptInterface.Bridges.inverse_map_set, MathOptInterface.Bridges.inverse_map_function, MathOptInterface.Bridges.adjoint_map_function and MathOptInterface.Bridges.inverse_adjoint_map_function. See the docstrings of the function to see which feature would be missing it it was not implemented for a given bridge.

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

Consider two type of sets S1, S2 and a linear mapping A 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-S2 constraints into F-in-S1 by mapping the function through A.

The linear map A is described by MathOptInterface.Bridges.map_set, MathOptInterface.Bridges.map_function. Implementing a method for these two functions is sufficient to bridge constraints. In order for the getters and setters of dual solutions, starting values, etc... to work as well a method for the following functions should be implemented as well: MathOptInterface.Bridges.inverse_map_set, MathOptInterface.Bridges.inverse_map_function, MathOptInterface.Bridges.adjoint_map_function and MathOptInterface.Bridges.inverse_adjoint_map_function. See the docstrings of the function to see which feature would be missing it it was not implemented for a given bridge.

MathOptInterface.Bridges.map_functionFunction
map_function(::Type{BT}, func) where {BT}

Return the image of func through the linear map A defined in Variable.SetMapBridge and Constraint.SetMapBridge. This is used for getting the MathOptInterface.ConstraintPrimal of variable bridges. For constraint bridges, this is used for bridging the constraint, setting the MathOptInterface.ConstraintFunction and MathOptInterface.ConstraintPrimalStart and modifying the function with MathOptInterface.modify.

map_function(::Type{BT}, func, i::IndexInVector) where {BT}

Return the scalar function at the ith index of the vector function that would be returned by map_function(BT, func) except that it may compute the ith element. This is used by bridged_function and for getting the MathOptInterface.VariablePrimal and MathOptInterface.VariablePrimalStart of variable bridges.

MathOptInterface.Bridges.inverse_map_functionFunction
inverse_map_function(::Type{BT}, func) where {BT}

Return the image of func through the inverse of the linear map A defined in Variable.SetMapBridge and Constraint.SetMapBridge. This is used by Variable.unbridged_map and for setting the MathOptInterface.VariablePrimalStart of variable bridges and for getting the MathOptInterface.ConstraintFunction, the MathOptInterface.ConstraintPrimal and the MathOptInterface.ConstraintPrimalStart of constraint bridges.

### Bridges implemented

MathOptInterface.Bridges.Constraint.FlipSignBridgeType
FlipSignBridge{T, S1, S2, F, G}

Bridge a G-in-S1 constraint into an F-in-S2 constraint by multiplying the function by -1 and taking the point reflection of the set across the origin. The flipped F-in-S constraint is stored in the constraint field by convention.

MathOptInterface.Bridges.Constraint.AbstractToIntervalBridgeType
AbstractToIntervalBridge{T, S1, F}

Bridge a F-in-Interval constraint into an F-in-Interval{T} constraint where we have either:

• S1 = MOI.GreaterThan{T}
• S1 = MOI.LessThan{T}

The F-in-Interval{T} constraint is stored in the constraint field by convention.

Warning

It is required that T be a AbstractFloat type because otherwise typemin and typemax would either be not implemented (e.g. BigInt) or would not give infinite value (e.g. Int). For this reason, this bridge is only added to MathOptInterface.Bridges.full_bridge_optimizer.

when T is a subtype of AbstractFloat.

MathOptInterface.Bridges.Constraint.GreaterToLessBridgeType
GreaterToLessBridge{
T,
F<:MOI.AbstractScalarFunction,
G<:MOI.AbstractScalarFunction
} <: FlipSignBridge{T, MOI.GreaterThan{T}, MOI.LessThan{T}, F, G}

Transforms a G-in-GreaterThan{T} constraint into an F-in-LessThan{T} constraint.

MathOptInterface.Bridges.Constraint.LessToGreaterBridgeType
LessToGreaterBridge{
T,
F<:MOI.AbstractScalarFunction,
G<:MOI.AbstractScalarFunction
} <: FlipSignBridge{T, MOI.LessThan{T}, MOI.GreaterThan{T}, F, G}

Transforms a G-in-LessThan{T} constraint into an F-in-GreaterThan{T} constraint.

MathOptInterface.Bridges.Constraint.NonnegToNonposBridgeType
NonnegToNonposBridge{
T,
F<:MOI.AbstractVectorFunction,
G<:MOI.AbstractVectorFunction
} <: FlipSignBridge{T, MOI.Nonnegatives, MOI.Nonpositives, F, G}

Transforms a G-in-Nonnegatives constraint into a F-in-Nonpositives constraint.

MathOptInterface.Bridges.Constraint.NonposToNonnegBridgeType
NonposToNonnegBridge{
T,
F<:MOI.AbstractVectorFunction,
G<:MOI.AbstractVectorFunction,
} <: FlipSignBridge{T, MOI.Nonpositives, MOI.Nonnegatives, F, G}

Transforms a G-in-Nonpositives constraint into a F-in-Nonnegatives constraint.

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

Transforms a constraint G-in-scalar_set_type(S, T) where S <: VectorLinearSet to F-in-S.

Examples

The constraint VariableIndex-in-LessThan{Float64} becomes VectorAffineFunction{Float64}-in-Nonpositives, where T = Float64, F = VectorAffineFunction{Float64}, S = Nonpositives, and G = VariableIndex.

MathOptInterface.Bridges.Constraint.ScalarSlackBridgeType
ScalarSlackBridge{T, F, S}

The ScalarSlackBridge converts a constraint G-in-S where G is a function different from VariableIndex into the constraints F-in-EqualTo{T} and VariableIndex-in-S.

F is the result of subtracting a VariableIndex from G. Typically G is the same as F, but that is not mandatory.

MathOptInterface.Bridges.Constraint.VectorSlackBridgeType
VectorSlackBridge{T, F, S}

The VectorSlackBridge converts a constraint G-in-S where G is a function different from VectorOfVariables into the constraints Fin-Zeros and VectorOfVariables-in-S.

F is the result of subtracting a VectorOfVariables from G. Typically G is the same as F, but that is not mandatory.

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

The SplitIntervalBridge splits a F-in-S constraint into a F-in-LS and a F-in-US constraint where we have either:

• S = MOI.Interval{T}, LS = MOI.GreaterThan{T} and US = MOI.LessThan{T},
• S = MOI.EqualTo{T}, LS = MOI.GreaterThan{T} and US = MOI.LessThan{T}, or
• S = MOI.Zeros, LS = MOI.Nonnegatives and US = MOI.Nonpositives.

For instance, if F is MOI.ScalarAffineFunction and S is MOI.Interval, it transforms the constraint $l ≤ ⟨a, x⟩ + α ≤ u$ into the constraints $⟨a, x⟩ + α ≥ l$ and $⟨a, x⟩ + α ≤ u$.

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 MathOptInterface.ConstraintSet is set, a lower or upper bound constraint may be deleted or created accordingly.

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

The RotatedSecondOrderCone is SecondOrderCone representable; see [BN01, p. 104]. Indeed, we have $2tu = (t/√2 + u/√2)^2 - (t/√2 - u/√2)^2$ hence

$$$2tu \ge \lVert x \rVert_2^2$$$

is equivalent to

$$$(t/√2 + u/√2)^2 \ge \lVert x \rVert_2^2 + (t/√2 - u/√2)^2.$$$

We can therefore use the transformation $(t, u, x) \mapsto (t/√2+u/√2, t/√2-u/√2, x)$. Note that the linear transformation is a symmetric involution (i.e. it is its own transpose and its own inverse). That means in particular that the norm of constraint primal and dual values are preserved by the tranformation.

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

Constraints of the form VectorOfVariables-in-SecondOrderCone can be transformed into a ScalarQuadraticFunction-in-LessThan and a ScalarAffineFunction-in-GreaterThan. Indeed, the definition of the second-order cone

$$$t \ge \lVert x \rVert_2 \ (1)$$$

is equivalent to

$$$\sum x_i^2 \le t^2 (2)$$$

with $t \ge 0$. (3)

Warning

This transformation starts from a convex constraint (1) and creates a non-convex constraint (2), because the Q matrix associated with the constraint (2) has one negative eigenvalue. This might be wrongly interpreted by a solver. Some solvers can look at (2) and understand that it is a second order cone, but this is not a general rule. For these reasons this bridge is not automatically added by MOI.Bridges.full_bridge_optimizer. Care is recommended when adding this bridge to a optimizer.

Constraints of the form VectorOfVariables-in-SecondOrderCone can be transformed into a ScalarQuadraticFunction-in-LessThan and a ScalarAffineFunction-in-GreaterThan. Indeed, the definition of the second-order cone

$$$2tu \ge \lVert x \rVert_2^2, t,u \ge 0 (1)$$$

is equivalent to

$$$\sum x_i^2 \le 2tu (2)$$$

with $t,u \ge 0$. (3)

WARNING This transformation starts from a convex constraint (1) and creates a non-convex constraint (2), because the Q matrix associated with the constraint 2 has two negative eigenvalues. This might be wrongly interpreted by a solver. Some solvers can look at (2) and understand that it is a rotated second order cone, but this is not a general rule. For these reasons, this bridge is not automatically added by MOI.Bridges.full_bridge_optimizer. Care is recommended when adding this bridge to an optimizer.

The set of points x satisfying the constraint

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

is a convex set if Q is positive semidefinite and is the union of two convex cones if a and b are zero (i.e. homogeneous case) and Q has only one negative eigenvalue. Currently, only the non-homogeneous transformation is implemented, see the Note section below for more details.

Non-homogeneous case

If Q is positive semidefinite, there exists U such that $Q = U^T U$, the inequality can then be rewritten as

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

which is equivalent to the membership of (1, -a^T x - b, Ux) to the rotated second-order cone.

Homogeneous case

If Q has only one negative eigenvalue, the set of x such that $x^T Q x \le 0$ is the union of a convex cone and its opposite. We can choose which one to model by checking the existence of bounds on variables as shown below.

Second-order cone

If Q is diagonal and has eigenvalues (1, 1, -1), the inequality $x^2 + x^2 \le z^2$ combined with $z \ge 0$ defines the Lorenz cone (i.e. the second-order cone) but when combined with $z \le 0$, it gives the opposite of the second order cone. Therefore, we need to check if the variable z has a lower bound 0 or an upper bound 0 in order to determine which cone is

Rotated second-order cone

The matrix Q corresponding to the inequality $x^2 \le 2yz$ has one eigenvalue 1 with eigenvectors (1, 0, 0) and (0, 1, -1) and one eigenvalue -1 corresponding to the eigenvector (0, 1, 1). Hence if we intersect this union of two convex cone with the halfspace $x + y \ge 0$, we get the rotated second-order cone and if we intersect it with the halfspace $x + y \le 0$ we get the opposite of the rotated second-order cone. Note that y and z have the same sign since yz is nonnegative hence $x + y \ge 0$ is equivalent to $x \ge 0$ and $y \ge 0$.

Note

The check for existence of bound can be implemented (but inefficiently) with the current interface but if bound is removed or transformed (e.g. ≤ 0 transformed into ≥ 0) then the bridge is no longer valid. For this reason the homogeneous version of the bridge is not implemented yet.

MathOptInterface.Bridges.Constraint.SOCtoPSDBridgeType

The SOCtoPSDBridge transforms the second order cone constraint $\lVert x \rVert \le t$ into the semidefinite cone constraints

$$$\begin{pmatrix} t & x^\top\\ x & tI \end{pmatrix} \succeq 0$$$

Indeed by the Schur Complement, it is positive definite iff

\begin{align*} tI & \succ 0\\ t - x^\top (tI)^{-1} x & \succ 0 \end{align*}

which is equivalent to

\begin{align*} t & > 0\\ t^2 & > x^\top x \end{align*}
Warning

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

MathOptInterface.Bridges.Constraint.RSOCtoPSDBridgeType

The RSOCtoPSDBridge transforms the second order cone constraint $\lVert x \rVert \le 2tu$ with $u \ge 0$ into the semidefinite cone constraints

$$$\begin{pmatrix} t & x^\top\\ x & 2uI \end{pmatrix} \succeq 0$$$

Indeed by the Schur Complement, it is positive definite iff

\begin{align*} uI & \succ 0\\ t - x^\top (2uI)^{-1} x & \succ 0 \end{align*}

which is equivalent to

\begin{align*} u & > 0\\ 2tu & > x^\top x \end{align*}
MathOptInterface.Bridges.Constraint.NormOneBridgeType
NormOneBridge{T}

The NormOneCone is representable with LP constraints, since $t \ge \sum_i \lvert x_i \rvert$ if and only if there exists a vector y such that $t \ge \sum_i y_i$ and $y_i \ge x_i$, $y_i \ge -x_i$ for all $i$.

MathOptInterface.Bridges.Constraint.GeoMeantoRelEntrBridgeType
GeoMeantoRelEntrBridge{T}

The geometric mean cone is representable with a relative entropy constraint and a nonnegative auxiliary variable.

This is because $u \le \prod_{i=1}^n w_i^{1/n}$ is equivalent to $y \ge 0$ and $0 \le u + y \le \prod_{i=1}^n w_i^{1/n}$, and the latter inequality is equivalent to $1 \le \prod_{i=1}^n (\frac{w_i}{u + y})^{1/n}$, which is equivalent to $0 \le \sum_{i=1}^n \log (\frac{w_i}{u + y})^{1/n}$, which is equivalent to $0 \ge \sum_{i=1}^n (u + y) \log (\frac{u + y}{w_i})$.

Thus $(u, w) \in GeometricMeanCone(1 + n)$ is representable as $y \ge 0$, $(0, w, (u + y) e) \in RelativeEntropyCone(1 + 2n)$, where $e$ is a vector of ones.

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

The GeometricMeanCone is SecondOrderCone representable; see [1, p. 105].

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 x_{21} \ge 0$ such that:

\begin{align*} t & \le x_{21},\\ x_{21}^4 & \le x_1 x_2 x_3 x_{21}. \end{align*}

Note that we need to create $x_{21}$ and not use $t^4$ directly as $t$ is allowed to be negative. Now, this is equivalent to:

\begin{align*} t & \le x_{21}/\sqrt{4},\\ x_{21}^2 & \le 2x_{11} x_{12},\\ x_{11}^2 & \le 2x_1 x_2, & x_{12}^2 & \le 2x_3(x_{21}/\sqrt{4}). \end{align*}

[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.RelativeEntropyBridgeType
RelativeEntropyBridge{T}

The RelativeEntropyCone is representable with exponential cone and LP constraints, since $u \ge \sum_{i=1}^n w_i \log (\frac{w_i}{v_i})$ if and only if there exists a vector $y$ such that $u \ge \sum_i y_i$ and $y_i \ge w_i \log (\frac{w_i}{v_i})$ or equivalently $v_i \ge w_i \exp (\frac{-y_i}{w_i})$ or equivalently $(-y_i, w_i, v_i) \in ExponentialCone$, for all $i$.

MathOptInterface.Bridges.Constraint.NormNuclearBridgeType
NormNuclearBridge{T}

The NormNuclearCone is representable with an SDP constraint and extra variables, since $t \ge \sum_i \sigma_i (X)$ if and only if there exists symmetric matrices $U, V$ such that $[U X^\top; X V] \succ 0$ and $t \ge (tr(U) + tr(V)) / 2$.

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}

The RootDetConeTriangle is representable by a PositiveSemidefiniteConeTriangle and an 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 & \le (Δ_{11} Δ_{22} \cdots Δ_{nn})^{1/n} \end{align*}

[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}

The LogDetConeTriangle is representable by a PositiveSemidefiniteConeTriangle and ExponentialCone constraints.

Indeed, $\log\det(X) = \log(\delta_1) + \cdots + \log(\delta_n)$ where $\delta_1$, ..., $\delta_n$ 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 & \le u \log(Δ_{11}/u) + u \log(Δ_{22}/u) + \cdots + u \log(Δ_{nn}/u) \end{align*}

[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}

The IndicatorActiveOnFalseBridge replaces an indicator constraint activated on 0 with a variable $z_0$ with the constraint activated on 1, with a variable $z_1$. It stores the added variable and added constraints:

• $z_1 \in \mathbb{B}$ in zero_one_cons
• $z_0 + z_1 == 1$ in indisjunction_cons
• The added ACTIVATE_ON_ONE indicator constraint in indicator_cons_index.
MathOptInterface.Bridges.Constraint.IndicatorSOS1BridgeType
IndicatorSOS1Bridge{T,S<:MOI.AbstractScalarSet}

The IndicatorSOS1Bridge replaces an indicator constraint of the following form: $z \in \mathbb{B}, z == 1 \implies f(x) \in S$ with a SOS1 constraint: $z \in \mathbb{B}, slack \text{ free}, f(x) + slack \in S, SOS1(slack, z)$.

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

The SemiToBinaryBridge replaces a Semicontinuous constraint: $x \in \mathsf{Semicontinuous}(l, u)$ is replaced by: $z \in \{0, 1\}$, $x \leq z \cdot u$, $x \geq z \cdot l$.

The SemiToBinaryBridge replaces a Semiinteger constraint: $x \in Semiinteger(l, u)$ is replaced by: $z \in \{0, 1\}$, $x \in \mathbb{Z}$, $x \leq z \cdot u$, $x \geq z \cdot l$.

MathOptInterface.Bridges.Constraint.ZeroOneBridgeType
ZeroOneBridge{T}

The ZeroOneBridge splits a MOI.VariableIndex-in-MOI.ZeroOne constraint into a MOI.VariableIndex-in-MOI.Integer constraint and a MOI.VariableIndex-in-MOI.Interval(0, 1) constraint.

## Variable bridges

MathOptInterface.Bridges.Variable.SingleBridgeOptimizerType
SingleBridgeOptimizer{BT<:AbstractBridge, OT<:MOI.ModelLike} <:
AbstractBridgeOptimizer

The SingleBridgeOptimizer bridges any constrained variables supported by the bridge BT. This is in contrast with the MathOptInterface.Bridges.LazyBridgeOptimizer which only bridges the constrained variables that are unsupported by the internal model, even if they are supported by one of its bridges.

Note

Two bridge optimizers using variable bridges cannot be used together as both of them assume that the underlying model only returns variable indices with nonnegative values.

### Bridges implemented

MathOptInterface.Bridges.Variable.FlipSignBridgeType
FlipSignBridge{T, S1, S2}

Bridge constrained variables in S1 into constrained variables in S2 by multiplying the variables by -1 and taking the point reflection of the set across the origin. The flipped MOI.VectorOfVariables-in-S constraint is stored in the flipped_constraint field by convention.

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

Transforms constrained variables in MathOptInterface.Zeros to zeros, which ends up creating no variables in the underlying model.

The bridged variables are therefore similar to parameters with zero values. Parameters with non-zero value can be created with constrained variables in MOI.EqualTo by combining a VectorizeBridge and this bridge. The functions cannot be unbridged, given a function, we cannot determine, if the bridged variables were used.

The dual values cannot be determined by the bridge but they can be determined by the bridged optimizer using MathOptInterface.Utilities.get_fallback if a CachingOptimizer is used (since ConstraintFunction cannot be got as functions cannot be unbridged).

MathOptInterface.Bridges.Variable.VectorizeBridgeType
VectorizeBridge{T, S}

Transforms a constrained variable in scalar_set_type(S, T) where S <: VectorLinearSet into a constrained vector of one variable in S. For instance, VectorizeBridge{Float64, MOI.Nonnegatives} transforms a constrained variable in MOI.GreaterThan{Float64} into a constrained vector of one variable in MOI.Nonnegatives.

## Objective bridges

### Bridges implemented

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

The SlackBridge converts an objective function of type G into a MOI.VariableIndex objective by creating a slack variable and a F-in-MOI.LessThan constraint for minimization or F-in-MOI.LessThan constraint for maximization where F is MOI.Utilities.promote_operation(-, T, G, MOI.VariableIndex}. Note that when using this bridge, changing the optimization sense is not supported. Set the sense to MOI.FEASIBILITY_SENSE first to delete the bridge in order to change the sense, then re-add the objective.