# The Bridges submodule

The `Bridges`

module simplifies the process of converting models between equivalent formulations.

Read our paper for more details on how bridges are implemented.

## Why bridges?

A constraint can often be written in a number of equivalent formulations. For example, the constraint $l \le a^\top x \le u$ (`ScalarAffineFunction`

-in-`Interval`

) could be re-formulated as two constraints: $a^\top x \ge l$ (`ScalarAffineFunction`

-in-`GreaterThan`

) and $a^\top x \le u$ (`ScalarAffineFunction`

-in-`LessThan`

). An alternative re-formulation is to add a dummy variable `y`

with the constraints $l \le y \le u$ (`VariableIndex`

-in-`Interval`

) and $a^\top x - y = 0$ (`ScalarAffineFunction`

-in-`EqualTo`

).

To avoid each solver having to code these transformations manually, MathOptInterface provides *bridges*.

A bridge is a small transformation from one constraint type to another (potentially collection of) constraint type.

Because these bridges are included in MathOptInterface, they can be re-used by any optimizer. Some bridges also implement constraint modifications and constraint primal and dual translations.

Several bridges can be used in combination to transform a single constraint into a form that the solver may understand. Choosing the bridges to use takes the form of finding a shortest path in the hyper-graph of bridges. The methodology is detailed in the MOI paper.

## The three types of bridges

There are three types of bridges in MathOptInterface:

- Constraint bridges
- Variable bridges
- Objective bridges

### Constraint bridges

Constraint bridges convert constraints formulated by the user into an equivalent form supported by the solver. Constraint bridges are subtypes of `Bridges.Constraint.AbstractBridge`

.

The equivalent formulation may add constraints (and possibly also variables) in the underlying model.

In particular, constraint bridges can focus on rewriting the function of a constraint, and do not change the set. Function bridges are subtypes of `Bridges.Constraint.AbstractFunctionConversionBridge`

.

Read the list of implemented constraint bridges for more details on the types of transformations that are available. Function bridges are `Bridges.Constraint.ScalarFunctionizeBridge`

and `Bridges.Constraint.VectorFunctionizeBridge`

.

### Variable bridges

Variable bridges convert variables added by the user, either free with `add_variable`

/`add_variables`

, or constrained with `add_constrained_variable`

/`add_constrained_variables`

, into an equivalent form supported by the solver. Variable bridges are subtypes of `Bridges.Variable.AbstractBridge`

.

The equivalent formulation may add constraints (and possibly also variables) in the underlying model.

Read the list of implemented variable bridges for more details on the types of transformations that are available.

### Objective bridges

Objective bridges convert the `ObjectiveFunction`

set by the user into an equivalent form supported by the solver. Objective bridges are subtypes of `Bridges.Objective.AbstractBridge`

.

The equivalent formulation may add constraints (and possibly also variables) in the underlying model.

Read the list of implemented objective bridges for more details on the types of transformations that are available.

## Bridges.`full_bridge_optimizer`

Unless you have an advanced use-case, this is probably the only function you need to care about.

To enable the full power of MathOptInterface's bridges, wrap an `optimizer`

in a `Bridges.full_bridge_optimizer`

.

```
julia> inner_optimizer = MOI.Utilities.Model{Float64}()
MOIU.Model{Float64}
├ ObjectiveSense: FEASIBILITY_SENSE
├ ObjectiveFunctionType: MOI.ScalarAffineFunction{Float64}
├ NumberOfVariables: 0
└ NumberOfConstraints: 0
julia> optimizer = MOI.Bridges.full_bridge_optimizer(inner_optimizer, Float64)
MOIB.LazyBridgeOptimizer{MOIU.Model{Float64}}
├ Variable bridges: none
├ Constraint bridges: none
├ Objective bridges: none
└ model: MOIU.Model{Float64}
├ ObjectiveSense: FEASIBILITY_SENSE
├ ObjectiveFunctionType: MOI.ScalarAffineFunction{Float64}
├ NumberOfVariables: 0
└ NumberOfConstraints: 0
```

Now, use `optimizer`

as normal, and bridging will happen lazily behind the scenes. By lazily, we mean that bridging will happen if and only if the constraint is not supported by the `inner_optimizer`

.

Most bridges are added by default in `Bridges.full_bridge_optimizer`

. However, for technical reasons, some bridges are not added by default. Three examples include `Bridges.Constraint.SOCtoPSDBridge`

, `Bridges.Constraint.SOCtoNonConvexQuadBridge`

and `Bridges.Constraint.RSOCtoNonConvexQuadBridge`

. See the docs of those bridges for more information.

## Add a single bridge

If you don't want to use `Bridges.full_bridge_optimizer`

, you can wrap an optimizer in a single bridge.

However, this will force the constraint to be bridged, even if the `inner_optimizer`

supports it.

```
julia> inner_optimizer = MOI.Utilities.Model{Float64}();
julia> optimizer = MOI.Bridges.Constraint.SplitInterval{Float64}(inner_optimizer);
julia> x = MOI.add_variable(optimizer)
MOI.VariableIndex(1)
julia> MOI.add_constraint(optimizer, x, MOI.Interval(0.0, 1.0))
MathOptInterface.ConstraintIndex{MathOptInterface.VariableIndex, MathOptInterface.Interval{Float64}}(1)
julia> MOI.get(optimizer, MOI.ListOfConstraintTypesPresent())
1-element Vector{Tuple{Type, Type}}:
(MathOptInterface.VariableIndex, MathOptInterface.Interval{Float64})
julia> MOI.get(inner_optimizer, MOI.ListOfConstraintTypesPresent())
2-element Vector{Tuple{Type, Type}}:
(MathOptInterface.VariableIndex, MathOptInterface.GreaterThan{Float64})
(MathOptInterface.VariableIndex, MathOptInterface.LessThan{Float64})
```

## Bridges.LazyBridgeOptimizer

If you don't want to use `Bridges.full_bridge_optimizer`

, but you need more than a single bridge (or you want the bridging to happen lazily), you can manually construct a `Bridges.LazyBridgeOptimizer`

.

First, wrap an inner optimizer:

```
julia> inner_optimizer = MOI.Utilities.Model{Float64}()
MOIU.Model{Float64}
├ ObjectiveSense: FEASIBILITY_SENSE
├ ObjectiveFunctionType: MOI.ScalarAffineFunction{Float64}
├ NumberOfVariables: 0
└ NumberOfConstraints: 0
julia> optimizer = MOI.Bridges.LazyBridgeOptimizer(inner_optimizer)
MOIB.LazyBridgeOptimizer{MOIU.Model{Float64}}
├ Variable bridges: none
├ Constraint bridges: none
├ Objective bridges: none
└ model: MOIU.Model{Float64}
├ ObjectiveSense: FEASIBILITY_SENSE
├ ObjectiveFunctionType: MOI.ScalarAffineFunction{Float64}
├ NumberOfVariables: 0
└ NumberOfConstraints: 0
```

Then use `Bridges.add_bridge`

to add individual bridges:

```
julia> MOI.Bridges.add_bridge(optimizer, MOI.Bridges.Constraint.SplitIntervalBridge{Float64})
julia> MOI.Bridges.add_bridge(optimizer, MOI.Bridges.Objective.FunctionizeBridge{Float64})
```

Now the constraints will be bridged only if needed:

```
julia> x = MOI.add_variable(optimizer)
MOI.VariableIndex(1)
julia> MOI.add_constraint(optimizer, x, MOI.Interval(0.0, 1.0))
MathOptInterface.ConstraintIndex{MathOptInterface.VariableIndex, MathOptInterface.Interval{Float64}}(1)
julia> MOI.get(optimizer, MOI.ListOfConstraintTypesPresent())
1-element Vector{Tuple{Type, Type}}:
(MathOptInterface.VariableIndex, MathOptInterface.Interval{Float64})
julia> MOI.get(inner_optimizer, MOI.ListOfConstraintTypesPresent())
1-element Vector{Tuple{Type, Type}}:
(MathOptInterface.VariableIndex, MathOptInterface.Interval{Float64})
```