Bridges

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.

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.

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.

add_bridge(b::LazyBridgeOptimizer, BT::Type{<:AbstractBridge})

Enable the use of the bridges of type BT by b.

remove_bridge(b::LazyBridgeOptimizer, BT::Type{<:AbstractBridge})

Disable the use of the bridges of type BT by b.

has_bridge(b::LazyBridgeOptimizer, BT::Type{<:AbstractBridge})

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

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}()).

See also ListOfNonstandardBridges.

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:

function MOI.get(::MyQuadraticOptimizer, ::ListOfNonstandardBridges{Float64})
    return Type[
        MOI.Bridges.Constraint.SOCtoNonConvexQuadBridge{Float64},
        MOI.Bridges.Constraint.RSOCtoNonConvexQuadBridge{Float64},
    ]
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

debug_supports_constraint(
    b::LazyBridgeOptimizer,
    F::Type{<:MOI.AbstractFunction},
    S::Type{<:MOI.AbstractSet};
    io::IO = Base.stdout,
)

Prints to io explanations for the value of MOI.supports_constraint with the same arguments.

debug_supports(
    b::LazyBridgeOptimizer,
    ::MOI.ObjectiveFunction{F};
    io::IO = Base.stdout,
) where F

Prints to io explanations for the value of MOI.supports with the same arguments.

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.

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.

bridged_function(b::AbstractBridgeOptimizer, value)::typeof(value)

Substitute any bridged MOI.VariableIndex in value by an equivalent expression in terms of variables of b.model.

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.

AbstractBridge

Subtype of MathOptInterface.Bridges.AbstractBridge for constraint bridges.

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.

SingleBridgeOptimizer{BT<:AbstractBridge, OT<:MOI.ModelLike} <:
AbstractBridgeOptimizer

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

add_all_bridges(bridged_model, ::Type{T}) where {T}

Add all bridges defined in the Bridges.Constraint submodule to bridged_model. The coefficient type used is T.

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.

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.

map_set(::Type{BT}, set) where {BT}

Return the image of set through the linear map A defined in Variable.SetMapBridge and Constraint.SetMapBridge. This is used for bridging the constraint and setting the MathOptInterface.ConstraintSet.

inverse_map_set(::Type{BT}, set) where {BT}

Return the preimage of set through the linear map A defined in Variable.SetMapBridge and Constraint.SetMapBridge. This is used for getting the MathOptInterface.ConstraintSet.

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.

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.

adjoint_map_function(::Type{BT}, func) where {BT}

Return the image of func through the adjoint of the linear map A defined in Variable.SetMapBridge and Constraint.SetMapBridge. This is used for getting the MathOptInterface.ConstraintDual and MathOptInterface.ConstraintDualStart of constraint bridges.

inverse_adjoint_map_function(::Type{BT}, func) where {BT}

Return the image of func through the inverse of the adjoint of the linear map A defined in Variable.SetMapBridge and Constraint.SetMapBridge. This is used for getting the MathOptInterface.ConstraintDual of variable bridges and setting the MathOptInterface.ConstraintDualStart of constraint bridges.

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.

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.

GreaterToIntervalBridge{T, F<:MOI.AbstractScalarFunction} <:
    AbstractToIntervalBridge{T, MOI.GreaterThan{T}, F}

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

LessToIntervalBridge{T, F<:MOI.AbstractScalarFunction} <:
    AbstractToIntervalBridge{T, MOI.LessThan{T}, F}

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

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.

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.

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.

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.

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.

ScalarizeBridge{T, F, S}

Transforms a constraint AbstractVectorFunction-in-vector_set_type(S) where S <: LPCone{T} to F-in-S.

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.

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.

ScalarFunctionizeBridge{T, S}

The ScalarFunctionizeBridge converts a constraint VariableIndex-in-S into the constraint ScalarAffineFunction{T}-in-S.

VectorFunctionizeBridge{T, S}

The VectorFunctionizeBridge converts a constraint VectorOfVariables-in-S into the constraint VectorAffineFunction{T}-in-S.

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

SOCtoRSOCBridge{T, F, G}

We simply do the inverse transformation of RSOCtoSOCBridge. In fact, as the transformation is an involution, we do the same transformation.

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.

SOCtoNonConvexQuadBridge{T}

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)

RSOCtoNonConvexQuadBridge{T}

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.

QuadtoSOCBridge{T}

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.

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*}\]

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*}\]

NormInfinityBridge{T}

The NormInfinityCone is representable with LP constraints, since $t \ge \max_i \lvert x_i \rvert$ if and only if $t \ge x_i$ and $t \ge -x_i$ for all $i$.

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

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.

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.

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

NormSpectralBridge{T}

The NormSpectralCone is representable with a PSD constraint, since $t \ge \sigma_1(X)$ if and only if $[tI X^\top; X tI] \succ 0$.

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

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.

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.

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

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.

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)$.

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

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.

AbstractBridge

Subtype of MathOptInterface.Bridges.AbstractBridge for variable bridges.

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.

add_all_bridges(bridged_model, ::Type{T}) where {T}

Add all bridges defined in the Bridges.Variable submodule to bridged_model. The coefficient type used is T.

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.

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

FreeBridge{T} <: Bridges.Variable.AbstractBridge

Transforms constrained variables in MOI.Reals to the difference of constrained variables in MOI.Nonnegatives.

NonposToNonnegBridge{T} <:
    FlipSignBridge{T, MOI.Nonpositives, MOI.Nonnegatives}

Transforms constrained variables in Nonpositives into constrained variables in Nonnegatives.

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.

SOCtoRSOCBridge{T} <: Bridges.Variable.SetMapBridge{T,MOI.RotatedSecondOrderCone,MOI.SecondOrderCone}

Same transformation as MOI.Bridges.Constraint.SOCtoRSOCBridge.

RSOCtoSOCBridge{T} <: Bridges.Variable.SetMapBridge{T,MOI.SecondOrderCone,MOI.RotatedSecondOrderCone}

Same transformation as MOI.Bridges.Constraint.RSOCtoSOCBridge.

RSOCtoPSDBridge{T} <: Bridges.Variable.AbstractBridge

Transforms constrained variables in MathOptInterface.RotatedSecondOrderCone to constrained variables in MathOptInterface.PositiveSemidefiniteConeTriangle.

AbstractBridge

Subtype of MathOptInterface.Bridges.AbstractBridge for objective bridges.

SingleBridgeOptimizer{BT<:AbstractBridge, OT<:MOI.ModelLike} <: AbstractBridgeOptimizer

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

add_all_bridges(bridged_model, ::Type{T}) where {T}

Add all bridges defined in the Bridges.Objective submodule to bridged_model. The coefficient type used is T.

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.

FunctionizeBridge{T}

The FunctionizeBridge converts a VariableIndex objective into a ScalarAffineFunction{T} objective.