List of bridges
This section describes the Bridges.AbstractBridge
s that are implemented in MathOptInterface.
Constraint bridges
These bridges are subtypes of Bridges.Constraint.AbstractBridge
.
MathOptInterface.Bridges.Constraint.GreaterToIntervalBridge
— TypeGreaterToIntervalBridge{T,F} <: Bridges.Constraint.AbstractBridge
GreaterToIntervalBridge
implements the following reformulations:
- $f(x) \ge l$ into $f(x) \in [l, \infty)$
Source node
GreaterToIntervalBridge
supports:
F
inMOI.GreaterThan{T}
Target nodes
GreaterToIntervalBridge
creates:
F
inMOI.Interval{T}
MathOptInterface.Bridges.Constraint.LessToIntervalBridge
— TypeLessToIntervalBridge{T,F} <: Bridges.Constraint.AbstractBridge
LessToIntervalBridge
implements the following reformulations:
- $f(x) \le u$ into $f(x) \in (-\infty, u]$
Source node
LessToIntervalBridge
supports:
F
inMOI.LessThan{T}
Target nodes
LessToIntervalBridge
creates:
F
inMOI.Interval{T}
MathOptInterface.Bridges.Constraint.GreaterToLessBridge
— TypeGreaterToLessBridge{T,F,G} <: Bridges.Constraint.AbstractBridge
GreaterToLessBridge
implements the following reformulation:
- $f(x) \ge l$ into $-f(x) \le -l$
Source node
GreaterToLessBridge
supports:
G
inMOI.GreaterThan{T}
Target nodes
GreaterToLessBridge
creates:
F
inMOI.LessThan{T}
MathOptInterface.Bridges.Constraint.LessToGreaterBridge
— TypeLessToGreaterBridge{T,F,G} <: Bridges.Constraint.AbstractBridge
LessToGreaterBridge
implements the following reformulation:
- $f(x) \le u$ into $-f(x) \ge -u$
Source node
LessToGreaterBridge
supports:
G
inMOI.LessThan{T}
Target nodes
LessToGreaterBridge
creates:
F
inMOI.GreaterThan{T}
MathOptInterface.Bridges.Constraint.NonnegToNonposBridge
— TypeNonnegToNonposBridge{T,F,G} <: Bridges.Constraint.AbstractBridge
NonnegToNonposBridge
implements the following reformulation:
- $f(x) \in \mathbb{R}_+$ into $-f(x) \in \mathbb{R}_-$
Source node
NonnegToNonposBridge
supports:
G
inMOI.Nonnegatives
Target nodes
NonnegToNonposBridge
creates:
F
inMOI.Nonpositives
MathOptInterface.Bridges.Constraint.NonposToNonnegBridge
— TypeNonposToNonnegBridge{T,F,G} <: Bridges.Constraint.AbstractBridge
NonposToNonnegBridge
implements the following reformulation:
- $f(x) \in \mathbb{R}_-$ into $-f(x) \in \mathbb{R}_+$
Source node
NonposToNonnegBridge
supports:
G
inMOI.Nonpositives
Target nodes
NonposToNonnegBridge
creates:
F
inMOI.Nonnegatives
MathOptInterface.Bridges.Constraint.VectorizeBridge
— TypeVectorizeBridge{T,F,S,G} <: Bridges.Constraint.AbstractBridge
VectorizeBridge
implements the following reformulations:
- $g(x) \ge a$ into $[g(x) - a] \in \mathbb{R}_+$
- $g(x) \le a$ into $[g(x) - a] \in \mathbb{R}_-$
- $g(x) == a$ into $[g(x) - a] \in \{0\}$
where T
is the coefficient type of g(x) - a
.
Source node
VectorizeBridge
supports:
G
inMOI.GreaterThan{T}
G
inMOI.LessThan{T}
G
inMOI.EqualTo{T}
Target nodes
VectorizeBridge
creates:
F
inS
, whereS
is one ofMOI.Nonnegatives
,MOI.Nonpositives
,MOI.Zeros
depending on the type of the input set.
MathOptInterface.Bridges.Constraint.ScalarizeBridge
— TypeScalarizeBridge{T,F,S}
ScalarizeBridge
implements the following reformulations:
- $f(x) - a \in \mathbb{R}_+$ into $f_i(x) \ge a_i$ for all $i$
- $f(x) - a \in \mathbb{R}_-$ into $f_i(x) \le a_i$ for all $i$
- $f(x) - a \in \{0\}$ into $f_i(x) == a_i$ for all $i$
Source node
ScalarizeBridge
supports:
G
inMOI.Nonnegatives{T}
G
inMOI.Nonpositives{T}
G
inMOI.Zeros{T}
Target nodes
ScalarizeBridge
creates:
F
inS
, whereS
is one ofMOI.GreaterThan{T}
,MOI.LessThan{T}
, andMOI.EqualTo{T}
, depending on the type of the input set.
MathOptInterface.Bridges.Constraint.ScalarSlackBridge
— TypeScalarSlackBridge{T,F,S} <: Bridges.Constraint.AbstractBridge
ScalarSlackBridge
implements the following reformulation:
- $f(x) \in S$ into $f(x) - y == 0$ and $y \in S$
Source node
ScalarSlackBridge
supports:
G
inS
, whereG
is notMOI.VariableIndex
andS
is notMOI.EqualTo
Target nodes
ScalarSlackBridge
creates:
F
inMOI.EqualTo{T}
MOI.VariableIndex
inS
MathOptInterface.Bridges.Constraint.VectorSlackBridge
— TypeVectorSlackBridge{T,F,S} <: Bridges.Constraint.AbstractBridge
VectorSlackBridge
implements the following reformulation:
- $f(x) \in S$ into $f(x) - y \in \{0\}$ and $y \in S$
Source node
VectorSlackBridge
supports:
G
inS
, whereG
is notMOI.VectorOfVariables
andS
is notMOI.Zeros
Target nodes
VectorSlackBridge
creates:
F
inMOI.Zeros
MOI.VectorOfVariables
inS
MathOptInterface.Bridges.Constraint.ScalarFunctionizeBridge
— TypeScalarFunctionizeBridge{T,S} = FunctionConversionBridge{T,MOI.ScalarAffineFunction{T},MOI.VariableIndex,S}
ScalarFunctionizeBridge
implements the following reformulations:
- $x \in S$ into $1x + 0 \in S$
Source node
ScalarFunctionizeBridge
supports:
MOI.VariableIndex
inS
Target nodes
ScalarFunctionizeBridge
creates:
MathOptInterface.Bridges.Constraint.VectorFunctionizeBridge
— TypeVectorFunctionizeBridge{T,S} = FunctionConversionBridge{T,MOI.VectorAffineFunction{T},S}
VectorFunctionizeBridge
implements the following reformulations:
- $x \in S$ into $Ix + 0 \in S$
Source node
VectorFunctionizeBridge
supports:
Target nodes
VectorFunctionizeBridge
creates:
MathOptInterface.Bridges.Constraint.ToScalarQuadraticBridge
— TypeToScalarQuadraticBridge{T,G,S} <: AbstractFunctionConversionBridge{G,S}
ToScalarQuadraticBridge
implements the following reformulation:
- $g(x) \in S$ into $f(x) \in S$
where g
is an abstract scalar function and f
is a MOI.ScalarQuadraticFunction
.
Source node
ToScalarQuadraticBridge
supports:
G<:AbstractScalarFunction
inS
Target nodes
ToScalarQuadraticBridge
creates:
MathOptInterface.Bridges.Constraint.ToVectorQuadraticBridge
— TypeToVectorQuadraticBridge{T,G,S} <: AbstractFunctionConversionBridge{G,S}
ToVectorQuadraticBridge
implements the following reformulation:
- $g(x) \in S$ into $f(x) \in S$
where g
is an abstract vector function and f
is a MOI.VectorQuadraticFunction
.
Source node
ToVectorQuadraticBridge
supports:
G<:AbstractVectorFunction
inS
Target nodes
ToVectorQuadraticBridge
creates:
MathOptInterface.Bridges.Constraint.ToScalarNonlinearBridge
— TypeToScalarNonlinearBridge{T,G,S} <: AbstractFunctionConversionBridge{G,S}
ToScalarNonlinearBridge
implements the following reformulation:
- $g(x) \in S$ into $f(x) \in S$
where g
is an abstract scalar function and f
is a MOI.ScalarNonlinearFunction
.
Source node
ToScalarNonlinearBridge
supports:
G<:AbstractScalarFunction
inS
Target nodes
ToScalarNonlinearBridge
creates:
MathOptInterface.Bridges.Constraint.FunctionConversionBridge
— TypeFunctionConversionBridge{T,F,G,S} <: AbstractFunctionConversionBridge{G,S}
FunctionConversionBridge
implements the following reformulations:
- $g(x) \in S$ into $f(x) \in S$
for these pairs of functions:
MOI.ScalarAffineFunction
to [
MOI.ScalarQuadraticFunction`](@ref)MOI.ScalarQuadraticFunction
toMOI.ScalarNonlinearFunction
MOI.VectorAffineFunction
toMOI.VectorQuadraticFunction
Source node
FunctionConversionBridge
supports:
G
inS
Target nodes
FunctionConversionBridge
creates:
F
inS
MathOptInterface.Bridges.Constraint.SplitComplexEqualToBridge
— TypeSplitComplexEqualToBridge{T,F,G} <: Bridges.Constraint.AbstractBridge
SplitComplexEqualToBridge
implements the following reformulation:
- $f(x) + g(x) * im = a + b * im$ into $f(x) = a$ and $g(x) = b$
Source node
SplitComplexEqualToBridge
supports:
where G
is a function with Complex
coefficients.
Target nodes
SplitComplexEqualToBridge
creates:
F
inMOI.EqualTo{T}
where F
is the type of the real/imaginary part of G
.
MathOptInterface.Bridges.Constraint.SplitComplexZerosBridge
— TypeSplitComplexZerosBridge{T,F,G} <: Bridges.Constraint.AbstractBridge
SplitComplexZerosBridge
implements the following reformulation:
- $f(x) \in \{0\}^n$ into $\text{Re}(f(x)) \in \{0\}^n$ and $\text{Im}(f(x)) \in \{0\}^n$
Source node
SplitComplexZerosBridge
supports:
G
inMOI.Zeros
where G
is a function with Complex
coefficients.
Target nodes
SplitComplexZerosBridge
creates:
F
inMOI.Zeros
where F
is the type of the real/imaginary part of G
.
MathOptInterface.Bridges.Constraint.SplitHyperRectangleBridge
— TypeSplitHyperRectangleBridge{T,G,F} <: Bridges.Constraint.AbstractBridge
SplitHyperRectangleBridge
implements the following reformulation:
- $f(x) \in \textsf{HyperRectangle}(l, u)$ to $[f(x) - l; u - f(x)] \in \mathbb{R}_+$.
Source node
SplitHyperRectangleBridge
supports:
F
inMOI.HyperRectangle
Target nodes
SplitHyperRectangleBridge
creates:
G
inMOI.Nonnegatives
MathOptInterface.Bridges.Constraint.SplitIntervalBridge
— TypeSplitIntervalBridge{T,F,S,LS,US} <: Bridges.Constraint.AbstractBridge
SplitIntervalBridge
implements the following reformulations:
- $l \le f(x) \le u$ into $f(x) \ge l$ and $f(x) \le u$
- $f(x) = b$ into $f(x) \ge b$ and $f(x) \le b$
- $f(x) \in \{0\}$ into $f(x) \in \mathbb{R}_+$ and $f(x) \in \mathbb{R}_-$
Source node
SplitIntervalBridge
supports:
F
inMOI.Interval{T}
F
inMOI.EqualTo{T}
F
inMOI.Zeros
Target nodes
SplitIntervalBridge
creates:
F
inMOI.LessThan{T}
F
inMOI.GreaterThan{T}
or
F
inMOI.Nonnegatives
F
inMOI.Nonpositives
If T<:AbstractFloat
and S
is MOI.Interval{T}
then no lower (resp. upper) bound constraint is created if the lower (resp. upper) bound is typemin(T)
(resp. typemax(T)
). Similarly, when MOI.ConstraintSet
is set, a lower or upper bound constraint may be deleted or created accordingly.
MathOptInterface.Bridges.Constraint.SOCtoRSOCBridge
— TypeSOCtoRSOCBridge{T,F,G} <: Bridges.Constraint.AbstractBridge
SOCtoRSOCBridge
implements the following reformulation:
- $||x||_2 \le t$ into $(t+x_1)(t-x_1)\ge ||(x_2\ldots,x_N)||_2^2$
Assumptions
SOCtoRSOCBridge
assumes that the length ofx
is at least one.
Source node
SOCtoRSOCBridge
supports:
G
inMOI.SecondOrderCone
Target node
SOCtoRSOCBridge
creates:
MathOptInterface.Bridges.Constraint.RSOCtoSOCBridge
— TypeRSOCtoSOCBridge{T,F,G} <: Bridges.Constraint.AbstractBridge
RSOCtoSOCBridge
implements the following reformulation:
- $||x||_2^2 \le 2tu$ into $||\frac{t - u}{\sqrt 2}, x||_2 \le \frac{t + u}{\sqrt 2}$
Source node
RSOCtoSOCBridge
supports:
Target node
RSOCtoSOCBridge
creates:
F
inMOI.SecondOrderCone
MathOptInterface.Bridges.Constraint.SOCtoNonConvexQuadBridge
— TypeSOCtoNonConvexQuadBridge{T} <: Bridges.Constraint.AbstractBridge
SOCtoNonConvexQuadBridge
implements the following reformulations:
- $||x||_2 \le t$ into $\sum x^2 - t^2 \le 0$ and $1t + 0 \ge 0$
The MOI.ScalarAffineFunction
$1t + 0$ is used in case the variable has other bound constraints.
This transformation starts from a convex constraint and creates a non-convex constraint. Unless the solver has explicit support for detecting second-order cones in quadratic form, this may (wrongly) be interpreted by the solver as being non-convex. Therefore, this bridge is not added automatically by MOI.Bridges.full_bridge_optimizer
. Care is recommended when adding this bridge to a optimizer.
Source node
SOCtoNonConvexQuadBridge
supports:
Target nodes
SOCtoNonConvexQuadBridge
creates:
MathOptInterface.Bridges.Constraint.RSOCtoNonConvexQuadBridge
— TypeRSOCtoNonConvexQuadBridge{T} <: Bridges.Constraint.AbstractBridge
RSOCtoNonConvexQuadBridge
implements the following reformulations:
- $||x||_2^2 \le 2tu$ into $\sum x^2 - 2tu \le 0$, $1t + 0 \ge 0$, and $1u + 0 \ge 0$.
The MOI.ScalarAffineFunction
s $1t + 0$ and $1u + 0$ are used in case the variables have other bound constraints.
This transformation starts from a convex constraint and creates a non-convex constraint. Unless the solver has explicit support for detecting rotated second-order cones in quadratic form, this may (wrongly) be interpreted by the solver as being non-convex. Therefore, this bridge is not added automatically by MOI.Bridges.full_bridge_optimizer
. Care is recommended when adding this bridge to a optimizer.
Source node
RSOCtoNonConvexQuadBridge
supports:
Target nodes
RSOCtoNonConvexQuadBridge
creates:
MathOptInterface.Bridges.Constraint.QuadtoSOCBridge
— TypeQuadtoSOCBridge{T} <: Bridges.Constraint.AbstractBridge
QuadtoSOCBridge
converts quadratic inequalities
\[\frac{1}{2}x^T Q x + a^T x \le ub\]
into MOI.RotatedSecondOrderCone
constraints, but it only applies when $Q$ is positive definite.
This is because, if Q
is positive definite, there exists U
such that $Q = U^T U$, and so the inequality can then be rewritten as;
\[\|U x\|_2^2 \le 2 (-a^T x + ub)\]
Therefore, QuadtoSOCBridge
implements the following reformulations:
- $\frac{1}{2}x^T Q x + a^T x \le ub$ into $(1, -a^T x + ub, Ux) \in RotatedSecondOrderCone$ where $Q = U^T U$
- $\frac{1}{2}x^T Q x + a^T x \ge lb$ into $(1, a^T x - lb, Ux) \in RotatedSecondOrderCone$ where $-Q = U^T U$
Source node
QuadtoSOCBridge
supports:
Target nodes
RelativeEntropyBridge
creates:
Errors
This bridge errors if Q
is not positive definite.
MathOptInterface.Bridges.Constraint.SOCtoPSDBridge
— TypeSOCtoPSDBridge{T,F,G} <: Bridges.Constraint.AbstractBridge
SOCtoPSDBridge
implements the following reformulation:
- $||x||_2 \le t$ into $\left[\begin{array}{c c}t & x^\top \\ x & t \mathbf{I}\end{array}\right]\succeq 0$
This bridge is not added by default by MOI.Bridges.full_bridge_optimizer
because bridging second order cone constraints to semidefinite constraints can be achieved by the SOCtoRSOCBridge
followed by the RSOCtoPSDBridge
, while creating a smaller semidefinite constraint.
Source node
SOCtoPSDBridge
supports:
G
inMOI.SecondOrderCone
Target nodes
SOCtoPSDBridge
creates:
MathOptInterface.Bridges.Constraint.RSOCtoPSDBridge
— TypeRSOCtoPSDBridge{T,F,G} <: Bridges.Constraint.AbstractBridge
RSOCtoPSDBridge
implements the following reformulation:
- $||x||_2^2 \le 2t\cdot u$ into $\left[\begin{array}{c c}t & x^\top \\ x & 2tu \mathbf{I}\end{array}\right]\succeq 0$
Source node
RSOCtoPSDBridge
supports:
Target nodes
RSOCtoPSDBridge
creates:
MathOptInterface.Bridges.Constraint.NormInfinityBridge
— TypeNormInfinityBridge{T,F,G} <: Bridges.Constraint.AbstractBridge
NormInfinityBridge
implements the following reformulation:
- $|x|_\infty \le t$ into $[t - x_i, t + x_i] \in \mathbb{R}_+$.
Source node
NormInfinityBridge
supports:
Target nodes
NormInfinityBridge
creates:
F
inMOI.Nonnegatives
MathOptInterface.Bridges.Constraint.NormOneBridge
— TypeNormOneBridge{T,F,G} <: Bridges.Constraint.AbstractBridge
NormOneBridge
implements the following reformulation:
- $\sum |x_i| \le t$ into $[t - \sum y_i, y_i - x_i, y_i + x_i] \in \mathbb{R}_+$.
Source node
NormOneBridge
supports:
G
inMOI.NormOneCone{T}
Target nodes
NormOneBridge
creates:
F
inMOI.Nonnegatives
MathOptInterface.Bridges.Constraint.NormToPowerBridge
— TypeNormToPowerBridge{T,F} <: Bridges.Constraint.AbstractBridge
NormToPowerBridge
implements the following reformulation:
- $(t, x) \in NormCone(p, 1+d)$ into $(r_i, t, x_i) \in PowerCone(1 / p)$ for all $i$, and $\sum\limits_i r_i == t$.
For details, see Alizadeh, F., and Goldfarb, D. (2001). "Second-order cone programming." Mathematical Programming, Series B, 95:3-51.
Source node
NormToPowerBridge
supports:
F
inMOI.NormCone
Target nodes
NormToPowerBridge
creates:
MathOptInterface.Bridges.Constraint.NormOneConeToNormConeBridge
— TypeNormOneConeToNormConeBridge{T,F} <: Bridges.Constraint.AbstractBridge
NormOneConeToNormConeBridge
implements the following reformulations:
- $(t, x) in NormOneCone(d)$ into $(t, x) in NormCone(1, d)$
Source node
NormOneConeToNormConeBridge
supports:
F
inMOI.NormOneCone
Target nodes
NormOneConeToNormConeBridge
creates:
F
inMOI.NormCone
MathOptInterface.Bridges.Constraint.SecondOrderConeToNormConeBridge
— TypeSecondOrderConeToNormConeBridge{T,F} <: Bridges.Constraint.AbstractBridge
SecondOrderConeToNormConeBridge
implements the following reformulations:
- $(t, x) in SecondOrderCone(d)$ into $(t, x) in NormCone(2, d)$
Source node
SecondOrderConeToNormConeBridge
supports:
F
inMOI.SecondOrderCone
Target nodes
SecondOrderConeToNormConeBridge
creates:
F
inMOI.NormCone
MathOptInterface.Bridges.Constraint.NormInfinityConeToNormConeBridge
— TypeNormInfinityConeToNormConeBridge{T,F} <: Bridges.Constraint.AbstractBridge
NormInfinityConeToNormConeBridge
implements the following reformulations:
- $(t, x) in NormInfinityCone(d)$ into $(t, x) in NormCone(Inf, d)$
Source node
NormInfinityConeToNormConeBridge
supports:
F
inMOI.NormInfinityCone
Target nodes
NormInfinityConeToNormConeBridge
creates:
F
inMOI.NormCone
MathOptInterface.Bridges.Constraint.GeoMeantoRelEntrBridge
— TypeGeoMeantoRelEntrBridge{T,F,G,H} <: Bridges.Constraint.AbstractBridge
GeoMeantoRelEntrBridge
implements the following reformulation:
- $(u, w) \in GeometricMeanCone$ into $(0, w, (u + y)\mathbf{1})\in RelativeEntropyCone$ and $y \ge 0$
Source node
GeoMeantoRelEntrBridge
supports:
Target nodes
GeoMeantoRelEntrBridge
creates:
G
inMOI.RelativeEntropyCone
F
inMOI.Nonnegatives
Derivation
The derivation of the bridge is as follows:
\[\begin{aligned} (u, w) \in GeometricMeanCone \iff & u \le \left(\prod_{i=1}^n w_i\right)^{1/n} \\ \iff & 0 \le u + y \le \left(\prod_{i=1}^n w_i\right)^{1/n}, y \ge 0 \\ \iff & 1 \le \frac{\left(\prod_{i=1}^n w_i\right)^{1/n}}{u + y}, y \ge 0 \\ \iff & 1 \le \left(\prod_{i=1}^n \frac{w_i}{u + y}\right)^{1/n}, y \ge 0 \\ \iff & 0 \le \sum_{i=1}^n \log\left(\frac{w_i}{u + y}\right), y \ge 0 \\ \iff & 0 \ge \sum_{i=1}^n \log\left(\frac{u + y}{w_i}\right), y \ge 0 \\ \iff & 0 \ge \sum_{i=1}^n (u + y) \log\left(\frac{u + y}{w_i}\right), y \ge 0 \\ \iff & (0, w, (u + y)\mathbf{1}) \in RelativeEntropyCone, y \ge 0 \\ \end{aligned}\]
This derivation assumes that $u + y > 0$, which is enforced by the relative entropy cone.
MathOptInterface.Bridges.Constraint.GeoMeanToPowerBridge
— TypeGeoMeanToPowerBridge{T,F} <: Bridges.Constraint.AbstractBridge
GeoMeanToPowerBridge
implements the following reformulation:
- $(y, x...) \in GeometricMeanCone(1+d)$ into $(x_1, t, y) \in PowerCone(1/d)$ and $(t, x_2, ..., x_d) in GeometricMeanCone(d)$, which is then recursively expanded into more
PowerCone
constraints.
Source node
GeoMeanToPowerBridge
supports:
Target nodes
GeoMeanToPowerBridge
creates:
MathOptInterface.Bridges.Constraint.GeoMeanBridge
— TypeGeoMeanBridge{T,F,G,H} <: Bridges.Constraint.AbstractBridge
GeoMeanBridge
implements a reformulation from MOI.GeometricMeanCone
into MOI.RotatedSecondOrderCone
.
The reformulation is best described in an example.
Consider the cone of dimension 4:
\[t \le \sqrt[3]{x_1 x_2 x_3}\]
This can be rewritten as $\exists y \ge 0$ such that:
\[\begin{align*} t & \le y,\\ y^4 & \le x_1 x_2 x_3 y. \end{align*}\]
Note that we need to create $y$ and not use $t^4$ directly because $t$ is allowed to be negative.
This is equivalent to:
\[\begin{align*} t & \le \frac{y_1}{\sqrt{4}},\\ y_1^2 & \le 2y_2 y_3,\\ y_2^2 & \le 2x_1 x_2, \\ y_3^2 & \le 2x_3(y_1/\sqrt{4}) \\ y & \ge 0. \end{align*}\]
More generally, you can show how the geometric mean code is recursively expanded into a set of new variables $y$ in MOI.Nonnegatives
, a set of MOI.RotatedSecondOrderCone
constraints, and a MOI.LessThan
constraint between $t$ and $y_1$.
Source node
GeoMeanBridge
supports:
Target nodes
GeoMeanBridge
creates:
F
inMOI.LessThan{T}
G
inMOI.RotatedSecondOrderCone
G
inMOI.Nonnegatives
MathOptInterface.Bridges.Constraint.RelativeEntropyBridge
— TypeRelativeEntropyBridge{T,F,G,H} <: Bridges.Constraint.AbstractBridge
RelativeEntropyBridge
implements the following reformulation that converts a MOI.RelativeEntropyCone
into an MOI.ExponentialCone
:
- $u \ge \sum_{i=1}^n w_i \log \left(\frac{w_i}{v_i}\right)$ into $y_i \ge 0$, $u \ge \sum_{i=1}^n y_i$, and $(-y_i, w_i, v_i) \in ExponentialCone$.
Source node
RelativeEntropyBridge
supports:
Target nodes
RelativeEntropyBridge
creates:
F
inMOI.GreaterThan{T}
G
inMOI.ExponentialCone
MathOptInterface.Bridges.Constraint.NormSpectralBridge
— TypeNormSpectralBridge{T,F,G} <: Bridges.Constraint.AbstractBridge
NormSpectralBridge
implements the following reformulation:
- $t \ge \sigma_1(X)$ into $\left[\begin{array}{c c}t\mathbf{I} & X^\top \\ X & t \mathbf{I}\end{array}\right] \succeq 0$
Source node
NormSpectralBridge
supports:
G
inMOI.NormSpectralCone
Target nodes
NormSpectralBridge
creates:
MathOptInterface.Bridges.Constraint.NormNuclearBridge
— TypeNormNuclearBridge{T,F,G,H} <: Bridges.Constraint.AbstractBridge
NormNuclearBridge
implements the following reformulation:
- $t \ge \sum_i \sigma_i (X)$ into $\left[\begin{array}{c c}U & X^\top \\ X & V\end{array}\right] \succeq 0$ and $2t \ge tr(U) + tr(V)$.
Source node
NormNuclearBridge
supports:
H
inMOI.NormNuclearCone
Target nodes
NormNuclearBridge
creates:
MathOptInterface.Bridges.Constraint.SquareBridge
— TypeSquareBridge{T,F,G,TT,ST} <: Bridges.Constraint.AbstractBridge
SquareBridge
implements the following reformulations:
- $(t, u, X) \in LogDetConeSquare$ into $(t, u, Y) in LogDetConeTriangle$
- $(t, X) \in RootDetConeSquare$ into $(t, Y) in RootDetConeTriangle$
- $X \in AbstractSymmetricMatrixSetSquare$ into $Y in AbstractSymmetricMatrixSetTriangle$
where $Y$ is the upper triangluar component of $X$.
In addition, constraints are added as necessary to constrain the matrix $X$ to be symmetric. For example, the constraint for the matrix:
\[\begin{pmatrix} 1 & 1 + x & 2 - 3x\\ 1 + x & 2 + x & 3 - x\\ 2 - 3x & 2 + x & 2x \end{pmatrix}\]
can be broken down to the constraint of the symmetric matrix
\[\begin{pmatrix} 1 & 1 + x & 2 - 3x\\ \cdot & 2 + x & 3 - x\\ \cdot & \cdot & 2x \end{pmatrix}\]
and the equality constraint between the off-diagonal entries (2, 3) and (3, 2) $3 - x == 2 + x$. Note that no symmetrization constraint needs to be added between the off-diagonal entries (1, 2) and (2, 1) or between (1, 3) and (3, 1) because the expressions are the same.
Source node
SquareBridge
supports:
F
inST
Target nodes
SquareBridge
creates:
G
inTT
MathOptInterface.Bridges.Constraint.HermitianToSymmetricPSDBridge
— TypeHermitianToSymmetricPSDBridge{T,F,G} <: Bridges.Constraint.AbstractBridge
HermitianToSymmetricPSDBridge
implements the following reformulation:
- Hermitian positive semidefinite
n x n
complex matrix to a symmetric positive semidefinite2n x 2n
real matrix.
See also MOI.Bridges.Variable.HermitianToSymmetricPSDBridge
.
Source node
HermitianToSymmetricPSDBridge
supports:
Target node
HermitianToSymmetricPSDBridge
creates:
Reformulation
The reformulation is best described by example.
The Hermitian matrix:
\[\begin{bmatrix} x_{11} & x_{12} + y_{12}im & x_{13} + y_{13}im\\ x_{12} - y_{12}im & x_{22} & x_{23} + y_{23}im\\ x_{13} - y_{13}im & x_{23} - y_{23}im & x_{33} \end{bmatrix}\]
is positive semidefinite if and only if the symmetric matrix:
\[\begin{bmatrix} x_{11} & x_{12} & x_{13} & 0 & y_{12} & y_{13} \\ & x_{22} & x_{23} & -y_{12} & 0 & y_{23} \\ & & x_{33} & -y_{13} & -y_{23} & 0 \\ & & & x_{11} & x_{12} & x_{13} \\ & & & & x_{22} & x_{23} \\ & & & & & x_{33} \end{bmatrix}\]
is positive semidefinite.
The bridge achieves this reformulation by constraining the above matrix to belong to the MOI.PositiveSemidefiniteConeTriangle(6)
.
MathOptInterface.Bridges.Constraint.SetDotScalingBridge
— TypeSetDotScalingBridge{T,S,F,G} <: Bridges.Constraint.AbstractBridge
SetDotScalingBridge
implements the reformulation from constraints in S
to constraints in MOI.Scaled{S}
.
Source node
SetDotScalingBridge
supports:
G
inS
Target node
SetDotScalingBridge
creates:
F
inMOI.Scaled{S}
MathOptInterface.Bridges.Constraint.SetDotInverseScalingBridge
— TypeSetDotInverseScalingBridge{T,S,F,G} <: Bridges.Constraint.AbstractBridge
SetDotInverseScalingBridge
implements the reformulation from constraints in the MOI.Scaled{S}
to constraints in the S
.
Source node
SetDotInverseScalingBridge
supports:
G
inMOI.Scaled{S}
Target node
SetDotInverseScalingBridge
creates:
F
inS
MathOptInterface.Bridges.Constraint.RootDetBridge
— TypeRootDetBridge{T,F,G,H} <: Bridges.Constraint.AbstractBridge
The MOI.RootDetConeTriangle
is representable by MOI.PositiveSemidefiniteConeTriangle
and MOI.GeometricMeanCone
constraints, see [1, p. 149].
Indeed, $t \le \det(X)^{1/n}$ if and only if there exists a lower triangular matrix $Δ$ such that:
\[\begin{align*} \begin{pmatrix} X & Δ\\ Δ^\top & \mathrm{Diag}(Δ) \end{pmatrix} & \succeq 0\\ (t, \mathrm{Diag}(Δ)) & \in GeometricMeanCone \end{align*}\]
Source node
RootDetBridge
supports:
Target nodes
RootDetBridge
creates:
[1] Ben-Tal, Aharon, and Arkadi Nemirovski. Lectures on modern convex optimization: analysis, algorithms, and engineering applications. Society for Industrial and Applied Mathematics, 2001.
MathOptInterface.Bridges.Constraint.LogDetBridge
— TypeLogDetBridge{T,F,G,H,I} <: Bridges.Constraint.AbstractBridge
The MOI.LogDetConeTriangle
is representable by MOI.PositiveSemidefiniteConeTriangle
and MOI.ExponentialCone
constraints.
Indeed, $\log\det(X) = \sum\limits_{i=1}^n \log(\delta_i)$ where $\delta_i$ are the eigenvalues of $X$.
Adapting the method from [1, p. 149], we see that $t \le u \log(\det(X/u))$ for $u > 0$ if and only if there exists a lower triangular matrix $Δ$ such that
\[\begin{align*} \begin{pmatrix} X & Δ\\ Δ^\top & \mathrm{Diag}(Δ) \end{pmatrix} & \succeq 0\\ t - \sum_{i=1}^n u \log\left(\frac{Δ_{ii}}{u}\right) & \le 0 \end{align*}\]
Which we reformulate further into
\[\begin{align*} \begin{pmatrix} X & Δ\\ Δ^\top & \mathrm{Diag}(Δ) \end{pmatrix} & \succeq 0\\ (l_i, u , Δ_{ii}) & \in ExponentialCone\quad \forall i \\ t - \sum_{i=1}^n l_i & \le 0 \end{align*}\]
Source node
LogDetBridge
supports:
Target nodes
LogDetBridge
creates:
[1] Ben-Tal, Aharon, and Arkadi Nemirovski. Lectures on modern convex optimization: analysis, algorithms, and engineering applications. Society for Industrial and Applied Mathematics, 2001.
MathOptInterface.Bridges.Constraint.IndicatorActiveOnFalseBridge
— TypeIndicatorActiveOnFalseBridge{T,F,S} <: Bridges.Constraint.AbstractBridge
IndicatorActiveOnFalseBridge
implements the following reformulation:
- $\neg z \implies {f(x) \in S}$ into $y \implies {f(x) \in S}$, $z + y = 1$, and $y \in \{0, 1\}$
Source node
IndicatorActiveOnFalseBridge
supports:
Target nodes
IndicatorActiveOnFalseBridge
creates:
MathOptInterface.Bridges.Constraint.IndicatorGreaterToLessThanBridge
— TypeIndicatorGreaterToLessThanBridge{T,A} <: Bridges.Constraint.AbstractBridge
IndicatorGreaterToLessThanBridge
implements the following reformulation:
- $z \implies {f(x) \ge l}$ into $z \implies {-f(x) \le -l}$
Source node
IndicatorGreaterToLessThanBridge
supports:
Target nodes
IndicatorGreaterToLessThanBridge
creates:
MathOptInterface.Bridges.Constraint.IndicatorLessToGreaterThanBridge
— TypeIndicatorLessToGreaterThanBridge{T,A} <: Bridges.Constraint.AbstractBridge
IndicatorLessToGreaterThanBridge
implements the following reformulations:
- $z \implies {f(x) \le u}$ into $z \implies {-f(x) \ge -u}$
Source node
IndicatorLessToGreaterThanBridge
supports:
Target nodes
IndicatorLessToGreaterThanBridge
creates:
MathOptInterface.Bridges.Constraint.IndicatorSOS1Bridge
— TypeIndicatorSOS1Bridge{T,S} <: Bridges.Constraint.AbstractBridge
IndicatorSOS1Bridge
implements the following reformulation:
- $z \implies {f(x) \in S}$ into $f(x) + y \in S$, $SOS1(y, z)$
This bridge assumes that the solver supports MOI.SOS1{T}
constraints in which one of the variables ($y$) is continuous.
Source node
IndicatorSOS1Bridge
supports:
Target nodes
IndicatorSOS1Bridge
creates:
MathOptInterface.Bridges.Constraint.SemiToBinaryBridge
— TypeSemiToBinaryBridge{T,S} <: Bridges.Constraint.AbstractBridge
SemiToBinaryBridge
implements the following reformulations:
- $x \in \{0\} \cup [l, u]$ into
\[\begin{aligned} x \leq z u \\ x \geq z l \\ z \in \{0, 1\} \end{aligned}\]
- $x \in \{0\} \cup \{l, \ldots, u\}$ into
\[\begin{aligned} x \leq z u \\ x \geq z l \\ z \in \{0, 1\} \\ x \in \mathbb{Z} \end{aligned}\]
Source node
SemiToBinaryBridge
supports:
Target nodes
SemiToBinaryBridge
creates:
MathOptInterface.Bridges.Constraint.ZeroOneBridge
— TypeZeroOneBridge{T} <: Bridges.Constraint.AbstractBridge
ZeroOneBridge
implements the following reformulation:
- $x \in \{0, 1\}$ into $x \in \mathbb{Z}$, $1x \in [0, 1]$.
ZeroOneBridge
adds a linear constraint instead of adding variable bounds to avoid conflicting with bounds set by the user.
Source node
ZeroOneBridge
supports:
Target nodes
ZeroOneBridge
creates:
MathOptInterface.Bridges.Constraint.IntegerToZeroOneBridge
— TypeIntegerToZeroOneBridge{T} <: Bridges.Constraint.AbstractBridge
IntegerToZeroOneBridge
implements the following reformulation:
- $x \in \mathbf{Z}$ into $y_i \in \{0, 1\}$, $x == lb + \sum 2^{i-1} y_i$.
Source node
IntegerToZeroOneBridge
supports:
VariableIndex
inMOI.Integer
Target nodes
IntegerToZeroOneBridge
creates:
Developer note
This bridge is implemented as a constraint bridge instead of a variable bridge because we don't want to substitute the linear combination of y
for every instance of x
. Doing so would be expensive and greatly reduce the sparsity of the constraints.
MathOptInterface.Bridges.Constraint.NumberConversionBridge
— TypeNumberConversionBridge{T,F1,S1,F2,S2} <: Bridges.Constraint.AbstractBridge
NumberConversionBridge
implements the following reformulation:
- $f1(x) \in S1$ to $f2(x) \in S2$
where f
and S
are the same functional form, but differ in their coefficient type.
Source node
NumberConversionBridge
supports:
F1
inS1
Target node
NumberConversionBridge
creates:
F2
inS2
MathOptInterface.Bridges.Constraint.AllDifferentToCountDistinctBridge
— TypeAllDifferentToCountDistinctBridge{T,F} <: Bridges.Constraint.AbstractBridge
AllDifferentToCountDistinctBridge
implements the following reformulations:
- $x \in \textsf{AllDifferent}(d)$ to $(n, x) \in \textsf{CountDistinct}(1+d)$ and $n = d$
- $f(x) \in \textsf{AllDifferent}(d)$ to $(d, f(x)) \in \textsf{CountDistinct}(1+d)$
Source node
AllDifferentToCountDistinctBridge
supports:
F
inMOI.AllDifferent
where F
is MOI.VectorOfVariables
or MOI.VectorAffineFunction{T}
.
Target nodes
AllDifferentToCountDistinctBridge
creates:
MathOptInterface.Bridges.Constraint.ReifiedAllDifferentToCountDistinctBridge
— TypeReifiedAllDifferentToCountDistinctBridge{T,F} <:
Bridges.Constraint.AbstractBridge
ReifiedAllDifferentToCountDistinctBridge
implements the following reformulations:
- $r \iff x \in \textsf{AllDifferent}(d)$ to $r \iff (n, x) \in \textsf{CountDistinct}(1+d)$ and $n = d$
- $r \iff f(x) \in \textsf{AllDifferent}(d)$ to $r \iff (d, f(x)) \in \textsf{CountDistinct}(1+d)$
Source node
ReifiedAllDifferentToCountDistinctBridge
supports:
where F
is MOI.VectorOfVariables
or MOI.VectorAffineFunction{T}
.
Target nodes
ReifiedAllDifferentToCountDistinctBridge
creates:
MathOptInterface.Bridges.Constraint.BinPackingToMILPBridge
— TypeBinPackingToMILPBridge{T,F} <: Bridges.Constraint.AbstractBridge
BinPackingToMILPBridge
implements the following reformulation:
- $x \in BinPacking(c, w)$ into a mixed-integer linear program.
Reformulation
The reformulation is non-trivial, and it depends on the finite domain of each variable $x_i$, which we as define $S_i = \{l_i,\ldots,u_i\}$.
First, we introduce new binary variables $z_{ij}$, which are $1$ if variable $x_i$ takes the value $j$ in the optimal solution and $0$ otherwise:
\[\begin{aligned} z_{ij} \in \{0, 1\} & \;\; \forall i \in 1\ldots d, j \in S_i \\ x_i - \sum\limits_{j\in S_i} j \cdot z_{ij} = 0 & \;\; \forall i \in 1\ldots d \\ \sum\limits_{j\in S_i} z_{ij} = 1 & \;\; \forall i \in 1\ldots d \\ \end{aligned}\]
Then, we add the capacity constraint for all possible bins $j$:
\[\sum\limits_{i} w_i z_{ij} \le c \forall j \in \bigcup_{i=1,\ldots,d} S_i\]
Source node
BinPackingToMILPBridge
supports:
F
inMOI.BinPacking{T}
Target nodes
BinPackingToMILPBridge
creates:
MathOptInterface.Bridges.Constraint.CircuitToMILPBridge
— TypeCircuitToMILPBridge{T,F} <: Bridges.Constraint.AbstractBridge
CircuitToMILPBridge
implements the following reformulation:
- $x \in \textsf{Circuit}(d)$ to the Miller-Tucker-Zemlin formulation of the Traveling Salesperson Problem.
Source node
CircuitToMILPBridge
supports:
F
inMOI.Circuit
where F
is MOI.VectorOfVariables
or MOI.VectorAffineFunction{T}
.
Target nodes
CircuitToMILPBridge
creates:
MathOptInterface.Bridges.Constraint.CountAtLeastToCountBelongsBridge
— TypeCountAtLeastToCountBelongsBridge{T,F} <: Bridges.Constraint.AbstractBridge
CountAtLeastToCountBelongsBridge
implements the following reformulation:
- $x \in \textsf{CountAtLeast}(n, d, \mathcal{S})$ to $(n_i, x_{d_i}) \in \textsf{CountBelongs}(1+d, \mathcal{S})$ and $n_i \ge n$ for all $i$.
Source node
CountAtLeastToCountBelongsBridge
supports:
F
inMOI.CountAtLeast
where F
is MOI.VectorOfVariables
or MOI.VectorAffineFunction{T}
.
Target nodes
CountAtLeastToCountBelongsBridge
creates:
MathOptInterface.Bridges.Constraint.CountBelongsToMILPBridge
— TypeCountBelongsToMILPBridge{T,F} <: Bridges.Constraint.AbstractBridge
CountBelongsToMILPBridge
implements the following reformulation:
- $(n, x) \in \textsf{CountBelongs}(1+d, \mathcal{S})$ into a mixed-integer linear program.
Reformulation
The reformulation is non-trivial, and it depends on the finite domain of each variable $x_i$, which we as define $S_i = \{l_i,\ldots,u_i\}$.
First, we introduce new binary variables $z_{ij}$, which are $1$ if variable $x_i$ takes the value $j$ in the optimal solution and $0$ otherwise:
\[\begin{aligned} z_{ij} \in \{0, 1\} & \;\; \forall i \in 1\ldots d, j \in S_i \\ x_i - \sum\limits_{j\in S_i} j \cdot z_{ij} = 0 & \;\; \forall i \in 1\ldots d \\ \sum\limits_{j\in S_i} z_{ij} = 1 & \;\; \forall i \in 1\ldots d \\ \end{aligned}\]
Finally, $n$ is constrained to be the number of $z_{ij}$ elements that are in $\mathcal{S}$:
\[n - \sum\limits_{i\in 1\ldots d, j \in \mathcal{S}} z_{ij} = 0\]
Source node
CountBelongsToMILPBridge
supports:
F
inMOI.CountBelongs
where F
is MOI.VectorOfVariables
or MOI.VectorAffineFunction{T}
.
Target nodes
CountBelongsToMILPBridge
creates:
MathOptInterface.Bridges.Constraint.CountDistinctToMILPBridge
— TypeCountDistinctToMILPBridge{T,F} <: Bridges.Constraint.AbstractBridge
CountDistinctToMILPBridge
implements the following reformulation:
- $(n, x) \in \textsf{CountDistinct}(1+d)$ into a mixed-integer linear program.
Reformulation
The reformulation is non-trivial, and it depends on the finite domain of each variable $x_i$, which we as define $S_i = \{l_i,\ldots,u_i\}$.
First, we introduce new binary variables $z_{ij}$, which are $1$ if variable $x_i$ takes the value $j$ in the optimal solution and $0$ otherwise:
\[\begin{aligned} z_{ij} \in \{0, 1\} & \;\; \forall i \in 1\ldots d, j \in S_i \\ x_i - \sum\limits_{j\in S_i} j \cdot z_{ij} = 0 & \;\; \forall i \in 1\ldots d \\ \sum\limits_{j\in S_i} z_{ij} = 1 & \;\; \forall i \in 1\ldots d \\ \end{aligned}\]
Then, we introduce new binary variables $y_j$, which are $1$ if a variable takes the value $j$ in the optimal solution and $0$ otherwise.
\[\begin{aligned} y_{j} \in \{0, 1\} & \;\; \forall j \in \bigcup_{i=1,\ldots,d} S_i \\ y_j \le \sum\limits_{i \in 1\ldots d: j \in S_i} z_{ij} \le M y_j & \;\; \forall j \in \bigcup_{i=1,\ldots,d} S_i\\ \end{aligned}\]
Finally, $n$ is constrained to be the number of $y_j$ elements that are non-zero:
\[n - \sum\limits_{j \in \bigcup_{i=1,\ldots,d} S_i} y_{j} = 0\]
Source node
CountDistinctToMILPBridge
supports:
F
inMOI.CountDistinct
where F
is MOI.VectorOfVariables
or MOI.VectorAffineFunction{T}
.
Target nodes
CountDistinctToMILPBridge
creates:
MathOptInterface.Bridges.Constraint.ReifiedCountDistinctToMILPBridge
— TypeReifiedCountDistinctToMILPBridge{T,F} <: Bridges.Constraint.AbstractBridge
ReifiedCountDistinctToMILPBridge
implements the following reformulation:
- $r \iff (n, x) \in \textsf{CountDistinct}(1+d)$ into a mixed-integer linear program.
Reformulation
The reformulation is non-trivial, and it depends on the finite domain of each variable $x_i$, which we as define $S_i = \{l_i,\ldots,u_i\}$.
First, we introduce new binary variables $z_{ij}$, which are $1$ if variable $x_i$ takes the value $j$ in the optimal solution and $0$ otherwise:
\[\begin{aligned} z_{ij} \in \{0, 1\} & \;\; \forall i \in 1\ldots d, j \in S_i \\ x_i - \sum\limits_{j\in S_i} j \cdot z_{ij} = 0 & \;\; \forall i \in 1\ldots d \\ \sum\limits_{j\in S_i} z_{ij} = 1 & \;\; \forall i \in 1\ldots d \\ \end{aligned}\]
Then, we introduce new binary variables $y_j$, which are $1$ if a variable takes the value $j$ in the optimal solution and $0$ otherwise.
\[\begin{aligned} y_{j} \in \{0, 1\} & \;\; \forall j \in \bigcup_{i=1,\ldots,d} S_i \\ y_j \le \sum\limits_{i \in 1\ldots d: j \in S_i} z_{ij} \le M y_j & \;\; \forall j \in \bigcup_{i=1,\ldots,d} S_i\\ \end{aligned}\]
Finally, $n$ is constrained to be the number of $y_j$ elements that are non-zero, with some slack:
\[n - \sum\limits_{j \in \bigcup_{i=1,\ldots,d} S_i} y_{j} = \delta^+ - \delta^-\]
And then the slack is constrained to respect the reif variable $r$:
\[\begin{aligned} d_1 \le \delta^+ \le M d_1 \\ d_2 \le \delta^- \le M d_s \\ d_1 + d_2 + r = 1 \\ d_1, d_2 \in \{0, 1\} \end{aligned}\]
Source node
ReifiedCountDistinctToMILPBridge
supports:
where F
is MOI.VectorOfVariables
or MOI.VectorAffineFunction{T}
.
Target nodes
ReifiedCountDistinctToMILPBridge
creates:
MathOptInterface.Bridges.Constraint.CountGreaterThanToMILPBridge
— TypeCountGreaterThanToMILPBridge{T,F} <: Bridges.Constraint.AbstractBridge
CountGreaterThanToMILPBridge
implements the following reformulation:
- $(c, y, x) \in CountGreaterThan()$ into a mixed-integer linear program.
Source node
CountGreaterThanToMILPBridge
supports:
F
inMOI.CountGreaterThan
Target nodes
CountGreaterThanToMILPBridge
creates:
MathOptInterface.Bridges.Constraint.TableToMILPBridge
— TypeTableToMILPBridge{T,F} <: Bridges.Constraint.AbstractBridge
TableToMILPBridge
implements the following reformulation:
- $x \in Table(t)$ into
\[\begin{aligned} z_{j} \in \{0, 1\} & \quad \forall i, j \\ \sum\limits_{j=1}^n z_{j} = 1 \\ \sum\limits_{j=1}^n t_{ij} z_{j} = x_i & \quad \forall i \end{aligned}\]
Source node
TableToMILPBridge
supports:
F
inMOI.Table{T}
Target nodes
TableToMILPBridge
creates:
Objective bridges
These bridges are subtypes of Bridges.Objective.AbstractBridge
.
MathOptInterface.Bridges.Objective.FunctionizeBridge
— TypeFunctionizeBridge{T}
FunctionizeBridge
implements the following reformulations:
- $\min \{x\}$ into $\min\{1x + 0\}$
- $\max \{x\}$ into $\max\{1x + 0\}$
where T
is the coefficient type of 1
and 0
.
Source node
FunctionizeBridge
supports:
Target nodes
FunctionizeBridge
creates:
- One objective node:
MOI.ObjectiveFunction{MOI.ScalarAffineFunction{T}}
MathOptInterface.Bridges.Objective.QuadratizeBridge
— TypeQuadratizeBridge{T}
QuadratizeBridge
implements the following reformulations:
- $\min \{a^\top x + b\}$ into $\min\{x^\top \mathbf{0} x + a^\top x + b\}$
- $\max \{a^\top x + b\}$ into $\max\{x^\top \mathbf{0} x + a^\top x + b\}$
where T
is the coefficient type of 0
.
Source node
QuadratizeBridge
supports:
Target nodes
QuadratizeBridge
creates:
- One objective node:
MOI.ObjectiveFunction{MOI.ScalarQuadraticFunction{T}}
MathOptInterface.Bridges.Objective.SlackBridge
— TypeSlackBridge{T,F,G}
SlackBridge
implements the following reformulations:
- $\min\{f(x)\}$ into $\min\{y\;|\; f(x) - y \le 0\}$
- $\max\{f(x)\}$ into $\max\{y\;|\; f(x) - y \ge 0\}$
where F
is the type of f(x) - y
, G
is the type of f(x)
, and T
is the coefficient type of f(x)
.
Source node
SlackBridge
supports:
Target nodes
SlackBridge
creates:
- One variable node:
MOI.VariableIndex
inMOI.Reals
- One objective node:
MOI.ObjectiveFunction{MOI.VariableIndex}
- One constraint node, that depends on the
MOI.ObjectiveSense
:F
-in-MOI.LessThan
ifMIN_SENSE
F
-in-MOI.GreaterThan
ifMAX_SENSE
When using this bridge, changing the optimization sense is not supported. Set the sense to MOI.FEASIBILITY_SENSE
first to delete the bridge, then set MOI.ObjectiveSense
and re-add the objective.
MathOptInterface.Bridges.Objective.VectorFunctionizeBridge
— TypeVectorFunctionizeBridge{T}
VectorFunctionizeBridge
implements the following reformulations:
- $\min \{x\}$ into $\min\{1x + 0\}$
- $\max \{x\}$ into $\max\{1x + 0\}$
where T
is the coefficient type of 1
and 0
.
Source node
VectorFunctionizeBridge
supports:
Target nodes
VectorFunctionizeBridge
creates:
- One objective node:
MOI.ObjectiveFunction{MOI.VectorAffineFunction{T}}
MathOptInterface.Bridges.Objective.VectorSlackBridge
— TypeVectorSlackBridge{T,F,G}
VectorSlackBridge
implements the following reformulations:
- $\min\{f(x)\}$ into $\min\{y\;|\; y - f(x) \in \mathbb{R}_+ \}$
- $\max\{f(x)\}$ into $\max\{y\;|\; f(x) - y \in \mathbb{R}_+ \}$
where F
is the type of f(x) - y
, G
is the type of f(x)
, and T
is the coefficient type of f(x)
.
Source node
VectorSlackBridge
supports:
Target nodes
VectorSlackBridge
creates:
- One variable node:
MOI.VectorOfVariables
inMOI.Reals
- One objective node:
MOI.ObjectiveFunction{MOI.VectorOfVariables}
- One constraint node:
F
-in-MOI.Nonnegatives
When using this bridge, changing the optimization sense is not supported. Set the sense to MOI.FEASIBILITY_SENSE
first to delete the bridge, then set MOI.ObjectiveSense
and re-add the objective.
Variable bridges
These bridges are subtypes of Bridges.Variable.AbstractBridge
.
MathOptInterface.Bridges.Variable.FreeBridge
— TypeFreeBridge{T} <: Bridges.Variable.AbstractBridge
FreeBridge
implements the following reformulation:
- $x \in \mathbb{R}$ into $y, z \ge 0$ with the substitution rule $x = y - z$,
where T
is the coefficient type of y - z
.
Source node
FreeBridge
supports:
Target nodes
FreeBridge
creates:
- One variable node:
MOI.VectorOfVariables
inMOI.Nonnegatives
MathOptInterface.Bridges.Variable.NonposToNonnegBridge
— TypeNonposToNonnegBridge{T} <: Bridges.Variable.AbstractBridge
NonposToNonnegBridge
implements the following reformulation:
- $x \in \mathbb{R}_-$ into $y \in \mathbb{R}_+$ with the substitution rule $x = -y$,
where T
is the coefficient type of -y
.
Source node
NonposToNonnegBridge
supports:
Target nodes
NonposToNonnegBridge
creates:
- One variable node:
MOI.VectorOfVariables
inMOI.Nonnegatives
,
MathOptInterface.Bridges.Variable.RSOCtoPSDBridge
— TypeRSOCtoPSDBridge{T} <: Bridges.Variable.AbstractBridge
RSOCtoPSDBridge
implements the following reformulation:
- $||x||_2^2 \le 2tu$ where $t, u \ge 0$ into $Y \succeq 0$, with the substitution rule: $Y = \left[\begin{array}{c c}t & x^\top \\ x & 2u \mathbf{I}\end{array}\right].$
Additional bounds are added to ensure the off-diagonals of the $2uI$ submatrix are 0
, and linear constraints are added to ennsure the diagonal of $2uI$ takes the same values.
As a special case, if $|x|| = 0$, then RSOCtoPSDBridge
reformulates into $(t, u) \in \mathbb{R}_+$.
Source node
RSOCtoPSDBridge
supports:
Target nodes
RSOCtoPSDBridge
creates:
- One variable node that depends on the input dimension:
MOI.VectorOfVariables
inMOI.Nonnegatives
if dimension is1
or2
MOI.VectorOfVariables
in
MOI.PositiveSemidefiniteConeTriangle
otherwise - The constraint node
MOI.VariableIndex
inMOI.EqualTo
- The constrant node
MOI.ScalarAffineFunction
inMOI.EqualTo
MathOptInterface.Bridges.Variable.RSOCtoSOCBridge
— TypeRSOCtoSOCBridge{T} <: Bridges.Variable.AbstractBridge
RSOCtoSOCBridge
implements the following reformulation:
- $||x||_2^2 \le 2tu$ into $||v||_2 \le w$, with the substitution rules $t = \frac{w}{\sqrt 2} + \frac{v_1}{\sqrt 2}$, $u = \frac{w}{\sqrt 2} - \frac{v_1}{\sqrt 2}$, and $x = (v_2,\ldots,v_N)$.
Source node
RSOCtoSOCBridge
supports:
Target node
RSOCtoSOCBridge
creates:
MathOptInterface.Bridges.Variable.SOCtoRSOCBridge
— TypeSOCtoRSOCBridge{T} <: Bridges.Variable.AbstractBridge
SOCtoRSOCBridge
implements the following reformulation:
- $||x||_2 \le t$ into $2uv \ge ||w||_2^2$, with the substitution rules $t = \frac{u}{\sqrt 2} + \frac{v}{\sqrt 2}$, $x = (\frac{u}{\sqrt 2} - \frac{v}{\sqrt 2}, w)$.
Assumptions
SOCtoRSOCBridge
assumes that $|x| \ge 1$.
Source node
SOCtoRSOCBridge
supports:
Target node
SOCtoRSOCBridge
creates:
MathOptInterface.Bridges.Variable.VectorizeBridge
— TypeVectorizeBridge{T,S} <: Bridges.Variable.AbstractBridge
VectorizeBridge
implements the following reformulations:
- $x \ge a$ into $[y] \in \mathbb{R}_+$ with the substitution rule $x = a + y$
- $x \le a$ into $[y] \in \mathbb{R}_-$ with the substitution rule $x = a + y$
- $x == a$ into $[y] \in \{0\}$ with the substitution rule $x = a + y$
where T
is the coefficient type of a + y
.
Source node
VectorizeBridge
supports:
MOI.VariableIndex
inMOI.GreaterThan{T}
MOI.VariableIndex
inMOI.LessThan{T}
MOI.VariableIndex
inMOI.EqualTo{T}
Target nodes
VectorizeBridge
creates:
- One variable node:
MOI.VectorOfVariables
inS
, whereS
is one ofMOI.Nonnegatives
,MOI.Nonpositives
,MOI.Zeros
depending on the type of $S$.
MathOptInterface.Bridges.Variable.ZerosBridge
— TypeZerosBridge{T} <: Bridges.Variable.AbstractBridge
ZerosBridge
implements the following reformulation:
- $x \in \{0\}$ into the substitution rule $x = 0$,
where T
is the coefficient type of 0
.
Source node
ZerosBridge
supports:
Target nodes
ZerosBridge
does not create target nodes. It replaces all instances of x
with 0
via substitution. This means that no variables are created in the underlying model.
Caveats
The bridged variables are similar to parameters with zero values. Parameters with non-zero values can be created with constrained variables in MOI.EqualTo
by combining a VectorizeBridge
and this bridge.
However, functions modified by ZerosBridge
cannot be unbridged. That is, for a given function, we cannot determine if the bridged variables were used.
A related implication is that this bridge does not support MOI.ConstraintDual
. However, if a MOI.Utilities.CachingOptimizer
is used, the dual can be determined by the bridged optimizer using MOI.Utilities.get_fallback
because the caching optimizer records the unbridged function.
MathOptInterface.Bridges.Variable.HermitianToSymmetricPSDBridge
— TypeHermitianToSymmetricPSDBridge{T} <: Bridges.Variable.AbstractBridge
HermitianToSymmetricPSDBridge
implements the following reformulation:
- Hermitian positive semidefinite
n x n
complex matrix to a symmetric positive semidefinite2n x 2n
real matrix satisfying equality constraints described below.
Source node
HermitianToSymmetricPSDBridge
supports:
Target node
HermitianToSymmetricPSDBridge
creates:
MOI.VectorOfVariables
inMOI.PositiveSemidefiniteConeTriangle
MOI.ScalarAffineFunction{T}
inMOI.EqualTo{T}
Reformulation
The reformulation is best described by example.
The Hermitian matrix:
\[\begin{bmatrix} x_{11} & x_{12} + y_{12}im & x_{13} + y_{13}im\\ x_{12} - y_{12}im & x_{22} & x_{23} + y_{23}im\\ x_{13} - y_{13}im & x_{23} - y_{23}im & x_{33} \end{bmatrix}\]
is positive semidefinite if and only if the symmetric matrix:
\[\begin{bmatrix} x_{11} & x_{12} & x_{13} & 0 & y_{12} & y_{13} \\ & x_{22} & x_{23} & -y_{12} & 0 & y_{23} \\ & & x_{33} & -y_{13} & -y_{23} & 0 \\ & & & x_{11} & x_{12} & x_{13} \\ & & & & x_{22} & x_{23} \\ & & & & & x_{33} \end{bmatrix}\]
is positive semidefinite.
The bridge achieves this reformulation by adding a new set of variables in MOI.PositiveSemidefiniteConeTriangle(6)
, and then adding three groups of equality constraints to:
- constrain the two
x
blocks to be equal - force the diagonal of the
y
blocks to be0
- force the lower triangular of the
y
block to be the negative of the upper triangle.