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.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.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.ComplexNormInfinityToSecondOrderConeBridge — Type
ComplexNormInfinityToSecondOrderConeBridge{T} <: Bridges.Constraint.AbstractBridge

ComplexNormInfinityToSecondOrderConeBridge implements the following reformulation:

  • $(t, x) \in NormInfinity(1+d)$ into $(t, real(x_i), imag(x_i)) \in SecondOrderCone()$ for all $i$.

Source node

ComplexNormInfinityToSecondOrderConeBridge supports:

Target nodes

ComplexNormInfinityToSecondOrderConeBridge 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.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.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.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.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.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.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.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.IndicatorSetMapBridge — Type
IndicatorSetMapBridge{T,A,S1,S2} <: Bridges.Constraint.AbstractBridge

IndicatorSetMapBridge implements the following reformulations:

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

Source node

IndicatorSetMapBridge supports:

Target nodes

IndicatorSetMapBridge 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
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.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.MultiSetMapBridge — Type
abstract type MultiSetMapBridge{T,S1,G} <: AbstractBridge end

Same as SetMapBridge but the output constraint type does not only depend on the input constraint type.

When subtyping MultiSetMapBridge, added_constraint_types and supports should additionally be implemented by the bridge.

For example, if a bridge BridgeType may create either a constraint of type F2-in-S2 or F3-in-S3, these methods should be implemented as follows:

function MOI.Bridges.added_constraint_types(
    ::Type{<:BridgeType{T,F2,F3}},
) where {T,F2,F3}
    return Tuple{Type,Type}[(F2, S2), (F3, S3)]
end

function MOI.supports(
    model::MOI.ModelLike,
    attr::Union{MOI.ConstraintPrimalStart,MOI.ConstraintDualStart},
    ::Type{<:BridgeType{T,F2,F3}},
) where {T,F2,F3}
    return MOI.supports(model, attr, MOI.ConstraintIndex{F2,S2}) ||
           MOI.supports(model, attr, MOI.ConstraintIndex{F3,S3})
end
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.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.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.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.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.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.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.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.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.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.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.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.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.SetMapBridge — Type
abstract type SetMapBridge{T,S2,S1,F,G} <: MultiSetMapBridge{T,S1,G} end

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

The linear map A is described by;

Implementing a method for these two functions is sufficient to bridge constraints. However, in order for the getters and setters of attributes such as dual solutions and starting values to work as well, a method for the following functions must be implemented:

See the docstrings of each function to see which feature would be missing if it was not implemented for a given bridge.

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

Objective bridges

These bridges are subtypes of Bridges.Objective.AbstractBridge.

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.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.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.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.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.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
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.SetMapBridge — Type
abstract type SetMapBridge{T,S1,S2} <: AbstractBridge end

Consider two type of sets, S1 and S2, and a linear mapping A such 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:

Implementing a method for these two functions is sufficient to bridge constrained variables. However, in order for the getters and setters of attributes such as dual solutions and starting values to work as well, a method for the following functions must be implemented:

See the docstrings of each function to see which feature would be missing if it was not implemented for a given bridge.

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