GitHub

List of bridges

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

Constraint bridges

These bridges are subtypes of Bridges.Constraint.AbstractBridge.

MathOptInterface.Bridges.Constraint.VectorizeBridge — Type
VectorizeBridge{T,F,S,G} <: Bridges.Constraint.AbstractBridge

VectorizeBridge implements the following reformulations:

  • $g(x) \ge a$ into $[g(x) - a] \in \mathbb{R}_+$
  • $g(x) \le a$ into $[g(x) - a] \in \mathbb{R}_-$
  • $g(x) == a$ into $[g(x) - a] \in \{0\}$

where T is the coefficient type of g(x) - a.

Source node

VectorizeBridge supports:

Target nodes

VectorizeBridge creates:

source
MathOptInterface.Bridges.Constraint.ScalarizeBridge — Type
ScalarizeBridge{T,F,S}

ScalarizeBridge implements the following reformulations:

  • $f(x) - a \in \mathbb{R}_+$ into $f_i(x) \ge a_i$ for all $i$
  • $f(x) - a \in \mathbb{R}_-$ into $f_i(x) \le a_i$ for all $i$
  • $f(x) - a \in \{0\}$ into $f_i(x) == a_i$ for all $i$

Source node

ScalarizeBridge supports:

Target nodes

ScalarizeBridge creates:

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

FunctionConversionBridge implements the following reformulations:

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

for these pairs of functions:

Source node

FunctionConversionBridge supports:

  • G in S

Target nodes

FunctionConversionBridge creates:

  • F in S
source
MathOptInterface.Bridges.Constraint.SplitComplexEqualToBridge — Type
SplitComplexEqualToBridge{T,F,G} <: Bridges.Constraint.AbstractBridge

SplitComplexEqualToBridge implements the following reformulation:

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

Source node

SplitComplexEqualToBridge supports:

where G is a function with Complex coefficients.

Target nodes

SplitComplexEqualToBridge creates:

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

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

SplitComplexZerosBridge implements the following reformulation:

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

Source node

SplitComplexZerosBridge supports:

where G is a function with Complex coefficients.

Target nodes

SplitComplexZerosBridge creates:

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

source
MathOptInterface.Bridges.Constraint.SplitIntervalBridge — Type
SplitIntervalBridge{T,F,S,LS,US} <: Bridges.Constraint.AbstractBridge

SplitIntervalBridge implements the following reformulations:

  • $l \le f(x) \le u$ into $f(x) \ge l$ and $f(x) \le u$
  • $f(x) = b$ into $f(x) \ge b$ and $f(x) \le b$
  • $f(x) \in \{0\}$ into $f(x) \in \mathbb{R}_+$ and $f(x) \in \mathbb{R}_-$

Source node

SplitIntervalBridge supports:

Target nodes

SplitIntervalBridge creates:

or

Note

If T<:AbstractFloat and S is MOI.Interval{T} then no lower (resp. upper) bound constraint is created if the lower (resp. upper) bound is typemin(T) (resp. typemax(T)). Similarly, when MOI.ConstraintSet is set, a lower or upper bound constraint may be deleted or created accordingly.

source
MathOptInterface.Bridges.Constraint.SOCtoNonConvexQuadBridge — Type
SOCtoNonConvexQuadBridge{T} <: Bridges.Constraint.AbstractBridge

SOCtoNonConvexQuadBridge implements the following reformulations:

  • $||x||_2 \le t$ into $\sum x^2 - t^2 \le 0$ and $1t + 0 \ge 0$

The MOI.ScalarAffineFunction $1t + 0$ is used in case the variable has other bound constraints.

Warning

This transformation starts from a convex constraint and creates a non-convex constraint. Unless the solver has explicit support for detecting second-order cones in quadratic form, this may (wrongly) be interpreted by the solver as being non-convex. Therefore, this bridge is not added automatically by MOI.Bridges.full_bridge_optimizer. Care is recommended when adding this bridge to a optimizer.

Source node

SOCtoNonConvexQuadBridge supports:

Target nodes

SOCtoNonConvexQuadBridge creates:

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

RSOCtoNonConvexQuadBridge implements the following reformulations:

  • $||x||_2^2 \le 2tu$ into $\sum x^2 - 2tu \le 0$, $1t + 0 \ge 0$, and $1u + 0 \ge 0$.

The MOI.ScalarAffineFunctions $1t + 0$ and $1u + 0$ are used in case the variables have other bound constraints.

Warning

This transformation starts from a convex constraint and creates a non-convex constraint. Unless the solver has explicit support for detecting rotated second-order cones in quadratic form, this may (wrongly) be interpreted by the solver as being non-convex. Therefore, this bridge is not added automatically by MOI.Bridges.full_bridge_optimizer. Care is recommended when adding this bridge to a optimizer.

Source node

RSOCtoNonConvexQuadBridge supports:

Target nodes

RSOCtoNonConvexQuadBridge creates:

source
MathOptInterface.Bridges.Constraint.QuadtoSOCBridge — Type
QuadtoSOCBridge{T} <: Bridges.Constraint.AbstractBridge

QuadtoSOCBridge converts quadratic inequalities

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

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

This is because, if Q is positive definite, there exists U such that $Q = U^T U$, and so the inequality can then be rewritten as;

\[\|U x\|_2^2 \le 2 (-a^T x + ub)\]

Therefore, QuadtoSOCBridge implements the following reformulations:

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

Source node

QuadtoSOCBridge supports:

Target nodes

RelativeEntropyBridge creates:

Errors

This bridge errors if Q is not positive definite.

source
MathOptInterface.Bridges.Constraint.SOCtoPSDBridge — Type
SOCtoPSDBridge{T,F,G} <: Bridges.Constraint.AbstractBridge

SOCtoPSDBridge implements the following reformulation:

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

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

Source node

SOCtoPSDBridge supports:

Target nodes

SOCtoPSDBridge creates:

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

NormToPowerBridge implements the following reformulation:

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

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

Source node

NormToPowerBridge supports:

Target nodes

NormToPowerBridge creates:

source
MathOptInterface.Bridges.Constraint.GeoMeantoRelEntrBridge — Type
GeoMeantoRelEntrBridge{T,F,G,H} <: Bridges.Constraint.AbstractBridge

GeoMeantoRelEntrBridge implements the following reformulation:

  • $(u, w) \in GeometricMeanCone$ into $(0, w, (u + y)\mathbf{1})\in RelativeEntropyCone$ and $y \ge 0$

Source node

GeoMeantoRelEntrBridge supports:

Target nodes

GeoMeantoRelEntrBridge creates:

Derivation

The derivation of the bridge is as follows:

\[\begin{aligned} (u, w) \in GeometricMeanCone \iff & u \le \left(\prod_{i=1}^n w_i\right)^{1/n} \\ \iff & 0 \le u + y \le \left(\prod_{i=1}^n w_i\right)^{1/n}, y \ge 0 \\ \iff & 1 \le \frac{\left(\prod_{i=1}^n w_i\right)^{1/n}}{u + y}, y \ge 0 \\ \iff & 1 \le \left(\prod_{i=1}^n \frac{w_i}{u + y}\right)^{1/n}, y \ge 0 \\ \iff & 0 \le \sum_{i=1}^n \log\left(\frac{w_i}{u + y}\right), y \ge 0 \\ \iff & 0 \ge \sum_{i=1}^n \log\left(\frac{u + y}{w_i}\right), y \ge 0 \\ \iff & 0 \ge \sum_{i=1}^n (u + y) \log\left(\frac{u + y}{w_i}\right), y \ge 0 \\ \iff & (0, w, (u + y)\mathbf{1}) \in RelativeEntropyCone, y \ge 0 \\ \end{aligned}\]

This derivation assumes that $u + y > 0$, which is enforced by the relative entropy cone.

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

GeoMeanToPowerBridge implements the following reformulation:

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

Source node

GeoMeanToPowerBridge supports:

Target nodes

GeoMeanToPowerBridge creates:

source
MathOptInterface.Bridges.Constraint.GeoMeanBridge — Type
GeoMeanBridge{T,F,G,H} <: Bridges.Constraint.AbstractBridge

GeoMeanBridge implements a reformulation from MOI.GeometricMeanCone into MOI.RotatedSecondOrderCone.

The reformulation is best described in an example.

Consider the cone of dimension 4:

\[t \le \sqrt[3]{x_1 x_2 x_3}\]

This can be rewritten as $\exists y \ge 0$ such that:

\[\begin{align*} t & \le y,\\ y^4 & \le x_1 x_2 x_3 y. \end{align*}\]

Note that we need to create $y$ and not use $t^4$ directly because $t$ is not allowed to be negative.

This is equivalent to:

\[\begin{align*} t & \le \frac{y_1}{\sqrt{4}},\\ y_1^2 & \le 2y_2 y_3,\\ y_2^2 & \le 2x_1 x_2, \\ y_3^2 & \le 2x_3(y_1/\sqrt{4}) \\ y & \ge 0. \end{align*}\]

More generally, you can show how the geometric mean code is recursively expanded into a set of new variables $y$ in MOI.Nonnegatives, a set of MOI.RotatedSecondOrderCone constraints, and a MOI.LessThan constraint between $t$ and $y_1$.

Source node

GeoMeanBridge supports:

Target nodes

GeoMeanBridge creates:

source
MathOptInterface.Bridges.Constraint.RelativeEntropyBridge — Type
RelativeEntropyBridge{T,F,G,H} <: Bridges.Constraint.AbstractBridge

RelativeEntropyBridge implements the following reformulation that converts a MOI.RelativeEntropyCone into an MOI.ExponentialCone:

  • $u \ge \sum_{i=1}^n w_i \log \left(\frac{w_i}{v_i}\right)$ into $y_i \ge 0$, $u \ge \sum_{i=1}^n y_i$, and $(-y_i, w_i, v_i) \in ExponentialCone$.

Source node

RelativeEntropyBridge supports:

Target nodes

RelativeEntropyBridge creates:

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

SquareBridge implements the following reformulations:

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

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

In addition, constraints are added as necessary to constrain the matrix $X$ to be symmetric. For example, the constraint for the matrix:

\[\begin{pmatrix} 1 & 1 + x & 2 - 3x\\ 1 + x & 2 + x & 3 - x\\ 2 - 3x & 2 + x & 2x \end{pmatrix}\]

can be broken down to the constraint of the symmetric matrix

\[\begin{pmatrix} 1 & 1 + x & 2 - 3x\\ \cdot & 2 + x & 3 - x\\ \cdot & \cdot & 2x \end{pmatrix}\]

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

Source node

SquareBridge supports:

  • F in ST

Target nodes

SquareBridge creates:

  • G in TT
source
MathOptInterface.Bridges.Constraint.HermitianToSymmetricPSDBridge — Type
HermitianToSymmetricPSDBridge{T,F,G} <: Bridges.Constraint.AbstractBridge

HermitianToSymmetricPSDBridge implements the following reformulation:

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

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

source
MathOptInterface.Bridges.Constraint.RootDetBridge — Type
RootDetBridge{T,F,G,H} <: Bridges.Constraint.AbstractBridge

The MOI.RootDetConeTriangle is representable by MOI.PositiveSemidefiniteConeTriangle and MOI.GeometricMeanCone constraints, see [1, p. 149].

Indeed, $t \le \det(X)^{1/n}$ if and only if there exists a lower triangular matrix $Δ$ such that:

\[\begin{align*} \begin{pmatrix} X & Δ\\ Δ^\top & \mathrm{Diag}(Δ) \end{pmatrix} & \succeq 0\\ (t, \mathrm{Diag}(Δ)) & \in GeometricMeanCone \end{align*}\]

Source node

RootDetBridge supports:

Target nodes

RootDetBridge creates:

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

source
MathOptInterface.Bridges.Constraint.LogDetBridge — Type
LogDetBridge{T,F,G,H,I} <: Bridges.Constraint.AbstractBridge

The MOI.LogDetConeTriangle is representable by MOI.PositiveSemidefiniteConeTriangle and MOI.ExponentialCone constraints.

Indeed, $\log\det(X) = \sum\limits_{i=1}^n \log(\delta_i)$ where $\delta_i$ are the eigenvalues of $X$.

Adapting the method from [1, p. 149], we see that $t \le u \log(\det(X/u))$ for $u > 0$ if and only if there exists a lower triangular matrix $Δ$ such that

\[\begin{align*} \begin{pmatrix} X & Δ\\ Δ^\top & \mathrm{Diag}(Δ) \end{pmatrix} & \succeq 0\\ t - \sum_{i=1}^n u \log\left(\frac{Δ_{ii}}{u}\right) & \le 0 \end{align*}\]

Which we reformulate further into

\[\begin{align*} \begin{pmatrix} X & Δ\\ Δ^\top & \mathrm{Diag}(Δ) \end{pmatrix} & \succeq 0\\ (l_i, u , Δ_{ii}) & \in ExponentialCone\quad \forall i \\ t - \sum_{i=1}^n l_i & \le 0 \end{align*}\]

Source node

LogDetBridge supports:

Target nodes

LogDetBridge creates:

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

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

IndicatorActiveOnFalseBridge implements the following reformulation:

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

Source node

IndicatorActiveOnFalseBridge supports:

Target nodes

IndicatorActiveOnFalseBridge creates:

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

IndicatorGreaterToLessThanBridge implements the following reformulation:

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

Source node

IndicatorGreaterToLessThanBridge supports:

Target nodes

IndicatorGreaterToLessThanBridge creates:

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

IndicatorLessToGreaterThanBridge implements the following reformulations:

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

Source node

IndicatorLessToGreaterThanBridge supports:

Target nodes

IndicatorLessToGreaterThanBridge creates:

source
MathOptInterface.Bridges.Constraint.IndicatorSOS1Bridge — Type
IndicatorSOS1Bridge{T,S} <: Bridges.Constraint.AbstractBridge

IndicatorSOS1Bridge implements the following reformulation:

  • $z \implies {f(x) \in S}$ into $f(x) + y \in S$, $SOS1(y, z)$
Warning

This bridge assumes that the solver supports MOI.SOS1{T} constraints in which one of the variables ($y$) is continuous.

Source node

IndicatorSOS1Bridge supports:

Target nodes

IndicatorSOS1Bridge creates:

source
MathOptInterface.Bridges.Constraint.SemiToBinaryBridge — Type
SemiToBinaryBridge{T,S} <: Bridges.Constraint.AbstractBridge

SemiToBinaryBridge implements the following reformulations:

  • $x \in \{0\} \cup [l, u]$ into

    \[\begin{aligned} x \leq z u \\ x \geq z l \\ z \in \{0, 1\} \end{aligned}\]

  • $x \in \{0\} \cup \{l, \ldots, u\}$ into

    \[\begin{aligned} x \leq z u \\ x \geq z l \\ z \in \{0, 1\} \\ x \in \mathbb{Z} \end{aligned}\]

Source node

SemiToBinaryBridge supports:

Target nodes

SemiToBinaryBridge creates:

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

ZeroOneBridge implements the following reformulation:

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

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

Source node

ZeroOneBridge supports:

Target nodes

ZeroOneBridge creates:

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

IntegerToZeroOneBridge implements the following reformulation:

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

Source node

IntegerToZeroOneBridge supports:

Target nodes

IntegerToZeroOneBridge creates:

Developer note

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

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

NumberConversionBridge implements the following reformulation:

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

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

Source node

NumberConversionBridge supports:

  • F1 in S1

Target node

NumberConversionBridge creates:

  • F2 in S2
source
MathOptInterface.Bridges.Constraint.AllDifferentToCountDistinctBridge — Type
AllDifferentToCountDistinctBridge{T,F} <: Bridges.Constraint.AbstractBridge

AllDifferentToCountDistinctBridge implements the following reformulations:

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

Source node

AllDifferentToCountDistinctBridge supports:

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

Target nodes

AllDifferentToCountDistinctBridge creates:

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

ReifiedAllDifferentToCountDistinctBridge implements the following reformulations:

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

Source node

ReifiedAllDifferentToCountDistinctBridge supports:

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

Target nodes

ReifiedAllDifferentToCountDistinctBridge creates:

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

BinPackingToMILPBridge implements the following reformulation:

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

Reformulation

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

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

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

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

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

Source node

BinPackingToMILPBridge supports:

Target nodes

BinPackingToMILPBridge creates:

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

CircuitToMILPBridge implements the following reformulation:

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

Source node

CircuitToMILPBridge supports:

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

Target nodes

CircuitToMILPBridge creates:

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

CountAtLeastToCountBelongsBridge implements the following reformulation:

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

Source node

CountAtLeastToCountBelongsBridge supports:

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

Target nodes

CountAtLeastToCountBelongsBridge creates:

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

CountBelongsToMILPBridge implements the following reformulation:

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

Reformulation

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

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

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

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

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

Source node

CountBelongsToMILPBridge supports:

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

Target nodes

CountBelongsToMILPBridge creates:

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

CountDistinctToMILPBridge implements the following reformulation:

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

Reformulation

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

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

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

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

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

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

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

Formulation (special case)

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

\[(x - y <= -1) \vee (y - x <= -1)\]

which is equivalent to (for suitable M):

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

Source node

CountDistinctToMILPBridge supports:

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

Target nodes

CountDistinctToMILPBridge creates:

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

ReifiedCountDistinctToMILPBridge implements the following reformulation:

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

Reformulation

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

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

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

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

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

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

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

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

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

Source node

ReifiedCountDistinctToMILPBridge supports:

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

Target nodes

ReifiedCountDistinctToMILPBridge creates:

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

CountGreaterThanToMILPBridge implements the following reformulation:

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

Source node

CountGreaterThanToMILPBridge supports:

Target nodes

CountGreaterThanToMILPBridge creates:

source
MathOptInterface.Bridges.Constraint.TableToMILPBridge — Type
TableToMILPBridge{T,F} <: Bridges.Constraint.AbstractBridge

TableToMILPBridge implements the following reformulation:

  • $x \in Table(t)$ into

    \[\begin{aligned} z_{j} \in \{0, 1\} & \quad \forall i, j \\ \sum\limits_{j=1}^n z_{j} = 1 \\ \sum\limits_{j=1}^n t_{ij} z_{j} = x_i & \quad \forall i \end{aligned}\]

Source node

TableToMILPBridge supports:

Target nodes

TableToMILPBridge creates:

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

SOS1ToMILPBridge implements the following reformulation:

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

Source node

SOS1ToMILPBridge supports:

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

Target nodes

SOS1ToMILPBridge creates:

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

SOS2ToMILPBridge implements the following reformulation:

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

Source node

SOS2ToMILPBridge supports:

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

Target nodes

SOS2ToMILPBridge creates:

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

IndicatorToMILPBridge implements the following reformulation:

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

Source node

IndicatorToMILPBridge supports:

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

Target nodes

IndicatorToMILPBridge creates:

source

Objective bridges

These bridges are subtypes of Bridges.Objective.AbstractBridge.

MathOptInterface.Bridges.Objective.QuadratizeBridge — Type
QuadratizeBridge{T,G} <: FunctionConversionBridge{T,MOI.ScalarQuadraticFunction{T},G}

QuadratizeBridge implements the following reformulations:

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

where T is the coefficient type of 0.

Source node

QuadratizeBridge supports:

Target nodes

QuadratizeBridge creates:

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

VectorFunctionizeBridge implements the following reformulations:

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

where T is the coefficient type of 1 and 0.

Source node

VectorFunctionizeBridge supports:

Target nodes

VectorFunctionizeBridge creates:

source
MathOptInterface.Bridges.Objective.FunctionConversionBridge — Type
FunctionConversionBridge{T,F,G} <: AbstractBridge

FunctionConversionBridge implements the following reformulations:

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

for these pairs of functions:

Source node

FunctionConversionBridge supports:

Target nodes

FunctionConversionBridge creates:

source
MathOptInterface.Bridges.Objective.SlackBridge — Type
SlackBridge{T,F,G}

SlackBridge implements the following reformulations:

  • $\min\{f(x)\}$ into $\min\{y\;|\; f(x) - y \le 0\}$
  • $\max\{f(x)\}$ into $\max\{y\;|\; f(x) - y \ge 0\}$

where F is the type of f(x) - y, G is the type of f(x), and T is the coefficient type of f(x).

Source node

SlackBridge supports:

Target nodes

SlackBridge creates:

Warning

When using this bridge, changing the optimization sense is not supported. Set the sense to MOI.FEASIBILITY_SENSE first to delete the bridge, then set MOI.ObjectiveSense and re-add the objective.

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

VectorSlackBridge implements the following reformulations:

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

where F is the type of f(x) - y, G is the type of f(x), and T is the coefficient type of f(x).

Source node

VectorSlackBridge supports:

Target nodes

VectorSlackBridge creates:

Warning

When using this bridge, changing the optimization sense is not supported. Set the sense to MOI.FEASIBILITY_SENSE first to delete the bridge, then set MOI.ObjectiveSense and re-add the objective.

source

Variable bridges

These bridges are subtypes of Bridges.Variable.AbstractBridge.

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

RSOCtoPSDBridge implements the following reformulation:

  • $||x||_2^2 \le 2tu$ where $t, u \ge 0$ into $Y \succeq 0$, with the substitution rule: $Y = \left[\begin{array}{c c}t & x^\top \\ x & 2u \mathbf{I}\end{array}\right].$

Additional bounds are added to ensure the off-diagonals of the $2uI$ submatrix are 0, and linear constraints are added to ensure the diagonal of $2uI$ takes the same values.

As a special case, if $|x|| = 0$, then RSOCtoPSDBridge reformulates into $(t, u) \in \mathbb{R}_+$.

Source node

RSOCtoPSDBridge supports:

Target nodes

RSOCtoPSDBridge creates:

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

RSOCtoSOCBridge implements the following reformulation:

  • $||x||_2^2 \le 2tu$ into $||v||_2 \le w$, with the substitution rules $t = \frac{w}{\sqrt 2} + \frac{v_1}{\sqrt 2}$, $u = \frac{w}{\sqrt 2} - \frac{v_1}{\sqrt 2}$, and $x = (v_2,\ldots,v_N)$.

Source node

RSOCtoSOCBridge supports:

Target node

RSOCtoSOCBridge creates:

source
MathOptInterface.Bridges.Variable.SOCtoRSOCBridge — Type
SOCtoRSOCBridge{T} <: Bridges.Variable.AbstractBridge

SOCtoRSOCBridge implements the following reformulation:

  • $||x||_2 \le t$ into $2uv \ge ||w||_2^2$, with the substitution rules $t = \frac{u}{\sqrt 2} + \frac{v}{\sqrt 2}$, $x = (\frac{u}{\sqrt 2} - \frac{v}{\sqrt 2}, w)$.

Assumptions

  • SOCtoRSOCBridge assumes that $|x| \ge 1$.

Source node

SOCtoRSOCBridge supports:

Target node

SOCtoRSOCBridge creates:

source
MathOptInterface.Bridges.Variable.VectorizeBridge — Type
VectorizeBridge{T,S} <: Bridges.Variable.AbstractBridge

VectorizeBridge implements the following reformulations:

  • $x \ge a$ into $[y] \in \mathbb{R}_+$ with the substitution rule $x = a + y$
  • $x \le a$ into $[y] \in \mathbb{R}_-$ with the substitution rule $x = a + y$
  • $x == a$ into $[y] \in \{0\}$ with the substitution rule $x = a + y$

where T is the coefficient type of a + y.

Source node

VectorizeBridge supports:

Target nodes

VectorizeBridge creates:

source
MathOptInterface.Bridges.Variable.ZerosBridge — Type
ZerosBridge{T} <: Bridges.Variable.AbstractBridge

ZerosBridge implements the following reformulation:

  • $x \in \{0\}$ into the substitution rule $x = 0$,

where T is the coefficient type of 0.

Source node

ZerosBridge supports:

Target nodes

ZerosBridge does not create target nodes. It replaces all instances of x with 0 via substitution. This means that no variables are created in the underlying model.

Caveats

The bridged variables are similar to parameters with zero values. Parameters with non-zero values can be created with constrained variables in MOI.EqualTo by combining a VectorizeBridge and this bridge.

However, functions modified by ZerosBridge cannot be unbridged. That is, for a given function, we cannot determine if the bridged variables were used.

A related implication is that this bridge does not support MOI.ConstraintDual. However, if a MOI.Utilities.CachingOptimizer is used, the dual can be determined by the bridged optimizer using MOI.Utilities.get_fallback because the caching optimizer records the unbridged function.

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

HermitianToSymmetricPSDBridge implements the following reformulation:

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

Source node

HermitianToSymmetricPSDBridge supports:

Target node

HermitianToSymmetricPSDBridge creates:

Reformulation

The reformulation is best described by example.

The Hermitian matrix:

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

is positive semidefinite if and only if the symmetric matrix:

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

is positive semidefinite.

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

  • constrain the two x blocks to be equal
  • force the diagonal of the y blocks to be 0
  • force the lower triangular of the y block to be the negative of the upper triangle.
source