The Bridges submodule

The Bridges module simplifies the process of converting models between equivalent formulations.

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:

1. Constraint bridges
2. Variable bridges
3. 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

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.

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