# Bridges

`MathOptInterface.Bridges.AbstractBridge`

— Type`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.AbstractBridgeOptimizer`

— Type`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.LazyBridgeOptimizer`

— Type`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.add_bridge`

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

Enable the use of the bridges of type `BT`

by `b`

.

`MathOptInterface.Bridges.remove_bridge`

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

Disable the use of the bridges of type `BT`

by `b`

.

`MathOptInterface.Bridges.has_bridge`

— Function`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_optimizer`

— Function`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`

.

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

`Constraint.SOCtoNonConvexQuadBridge`

,`Constraint.RSOCtoNonConvexQuadBridge`

and`Constraint.SOCtoPSDBridge`

.- The subtypes of
`Constraint.AbstractToIntervalBridge`

(i.e.`Constraint.GreaterToIntervalBridge`

and`Constraint.LessToIntervalBridge`

) if`T`

is not a subtype of`AbstractFloat`

.

`MathOptInterface.Bridges.ListOfNonstandardBridges`

— Type`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:

- implemented in
`MOI.Bridges`

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

`MathOptInterface.Bridges.debug_supports_constraint`

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

`MathOptInterface.Bridges.debug_supports`

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

`MathOptInterface.Bridges.bridged_variable_function`

— Function```
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_function`

— Function```
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.bridged_function`

— Function`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`

.

`MathOptInterface.Bridges.Variable.unbridged_map`

— Functionunbridged_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 `i`

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

— Type`AbstractBridge`

Subtype of `MathOptInterface.Bridges.AbstractBridge`

for constraint bridges.

`MathOptInterface.Bridges.Constraint.AbstractFunctionConversionBridge`

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

`MathOptInterface.Bridges.Constraint.SingleBridgeOptimizer`

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

`MathOptInterface.Bridges.Constraint.add_all_bridges`

— Function`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`

.

### SetMap bridges

`MathOptInterface.Bridges.Variable.SetMapBridge`

— Type`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.SetMapBridge`

— Type`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_set`

— Function`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`

.

`MathOptInterface.Bridges.inverse_map_set`

— Function`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`

.

`MathOptInterface.Bridges.map_function`

— Function`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 `i`

th index of the vector function that would be returned by `map_function(BT, func)`

except that it may compute the `i`

th element. This is used by `bridged_function`

and for getting the `MathOptInterface.VariablePrimal`

and `MathOptInterface.VariablePrimalStart`

of variable bridges.

`MathOptInterface.Bridges.inverse_map_function`

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

`MathOptInterface.Bridges.adjoint_map_function`

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

`MathOptInterface.Bridges.inverse_adjoint_map_function`

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

### Bridges implemented

`MathOptInterface.Bridges.Constraint.FlipSignBridge`

— Type`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.AbstractToIntervalBridge`

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

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

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

`MathOptInterface.Bridges.Constraint.LessToIntervalBridge`

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

`MathOptInterface.Bridges.Constraint.GreaterToLessBridge`

— Type```
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.LessToGreaterBridge`

— Type```
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.NonnegToNonposBridge`

— Type```
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.NonposToNonnegBridge`

— Type```
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.VectorizeBridge`

— Type`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.ScalarizeBridge`

— Type`ScalarizeBridge{T, F, S}`

Transforms a constraint `AbstractVectorFunction`

-in-`vector_set_type(S)`

where `S <: LPCone{T}`

to `F`

-in-`S`

.

`MathOptInterface.Bridges.Constraint.ScalarSlackBridge`

— Type`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.VectorSlackBridge`

— Type`VectorSlackBridge{T, F, S}`

The `VectorSlackBridge`

converts a constraint `G`

-in-`S`

where `G`

is a function different from `VectorOfVariables`

into the constraints `F`

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

— Type`ScalarFunctionizeBridge{T, S}`

The `ScalarFunctionizeBridge`

converts a constraint `VariableIndex`

-in-`S`

into the constraint `ScalarAffineFunction{T}`

-in-`S`

.

`MathOptInterface.Bridges.Constraint.VectorFunctionizeBridge`

— Type`VectorFunctionizeBridge{T, S}`

The `VectorFunctionizeBridge`

converts a constraint `VectorOfVariables`

-in-`S`

into the constraint `VectorAffineFunction{T}`

-in-`S`

.

`MathOptInterface.Bridges.Constraint.SplitIntervalBridge`

— Type`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$.

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

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

`MathOptInterface.Bridges.Constraint.RSOCtoSOCBridge`

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

`MathOptInterface.Bridges.Constraint.SOCtoNonConvexQuadBridge`

— Type`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)

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.

`MathOptInterface.Bridges.Constraint.RSOCtoNonConvexQuadBridge`

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

`MathOptInterface.Bridges.Constraint.QuadtoSOCBridge`

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

`MathOptInterface.Bridges.Constraint.SOCtoPSDBridge`

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

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

— TypeThe `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.NormInfinityBridge`

— Type`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$.

`MathOptInterface.Bridges.Constraint.NormOneBridge`

— Type`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.GeoMeantoRelEntrBridge`

— Type`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.GeoMeanBridge`

— Type`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.RelativeEntropyBridge`

— Type`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.NormSpectralBridge`

— Type`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$.

`MathOptInterface.Bridges.Constraint.NormNuclearBridge`

— Type`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.SquareBridge`

— Type```
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.RootDetBridge`

— Type`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.LogDetBridge`

— Type`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.IndicatorActiveOnFalseBridge`

— Type`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 `
`in`

disjunction_cons` - The added
`ACTIVATE_ON_ONE`

indicator constraint in`indicator_cons_index`

.

`MathOptInterface.Bridges.Constraint.IndicatorSOS1Bridge`

— Type`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.SemiToBinaryBridge`

— Type`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.ZeroOneBridge`

— Type`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.AbstractBridge`

— Type`AbstractBridge`

Subtype of `MathOptInterface.Bridges.AbstractBridge`

for variable bridges.

`MathOptInterface.Bridges.Variable.SingleBridgeOptimizer`

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

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.

`MathOptInterface.Bridges.Variable.add_all_bridges`

— Function`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`

.

### Bridges implemented

`MathOptInterface.Bridges.Variable.FlipSignBridge`

— Type`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.ZerosBridge`

— Type`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.FreeBridge`

— Type`FreeBridge{T} <: Bridges.Variable.AbstractBridge`

Transforms constrained variables in `MOI.Reals`

to the difference of constrained variables in `MOI.Nonnegatives`

.

`MathOptInterface.Bridges.Variable.NonposToNonnegBridge`

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

Transforms constrained variables in `Nonpositives`

into constrained variables in `Nonnegatives`

.

`MathOptInterface.Bridges.Variable.VectorizeBridge`

— Type`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`

.

`MathOptInterface.Bridges.Variable.SOCtoRSOCBridge`

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

Same transformation as `MOI.Bridges.Constraint.SOCtoRSOCBridge`

.

`MathOptInterface.Bridges.Variable.RSOCtoSOCBridge`

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

Same transformation as `MOI.Bridges.Constraint.RSOCtoSOCBridge`

.

`MathOptInterface.Bridges.Variable.RSOCtoPSDBridge`

— Type`RSOCtoPSDBridge{T} <: Bridges.Variable.AbstractBridge`

Transforms constrained variables in `MathOptInterface.RotatedSecondOrderCone`

to constrained variables in `MathOptInterface.PositiveSemidefiniteConeTriangle`

.

## Objective bridges

`MathOptInterface.Bridges.Objective.AbstractBridge`

— Type`AbstractBridge`

Subtype of `MathOptInterface.Bridges.AbstractBridge`

for objective bridges.

`MathOptInterface.Bridges.Objective.SingleBridgeOptimizer`

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

`MathOptInterface.Bridges.Objective.add_all_bridges`

— Function`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`

.

### Bridges implemented

`MathOptInterface.Bridges.Objective.SlackBridge`

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

`MathOptInterface.Bridges.Objective.FunctionizeBridge`

— Type`FunctionizeBridge{T}`

The `FunctionizeBridge`

converts a `VariableIndex`

objective into a `ScalarAffineFunction{T}`

objective.