Lighter bridges for a brighter life

[blegat]

When writing a solver wrapper, we often wonder whether to use bridges or not for a given constraint types that is not natively supported by the solver.
Using a bridge has the advantage of making the solver wrapper simpler and more maintainable but sometimes, when the constraint can be transformed to a supported one easily, we are tempted to support this constraint type too even if it is not supported by the solver to make sure that the transformation is efficiently.

Let's take ECOS to illustrate this. ECOS natively supports 4 types of constraints: VectorAffineFunction in Zeros, Nonnegatives, SecondOrderCone and ExponentialCone.

a) However, we may be tempted to also support VectorOfVariables in these sets since the transformation from VectorOfVariables to VectorAffineFunction is trivial:
https://github.com/JuliaOpt/ECOS.jl/blob/db356d4771c6f6f89e440db72be845ae57c4dcf9/src/MOIWrapper.jl#L170
It is one line but we need to allocate a new vector affine function so in fact it may be not that efficient, see below.
b) We may also be tempted to support Nonpositives since we just need to flip the sign to obtain Nonnegatives:
https://github.com/JuliaOpt/ECOS.jl/blob/db356d4771c6f6f89e440db72be845ae57c4dcf9/src/MOIWrapper.jl#L133
Again, we do -coeffficients with the vector of coefficients so it actually does a copy of the vector of coefficients which is not that efficient.
c) We can then also support scalar constraints such as SingleVariable, ScalarAffineFunction in EqualTo, LessThan, GreaterThan.
https://github.com/JuliaOpt/ECOS.jl/blob/db356d4771c6f6f89e440db72be845ae57c4dcf9/src/MOIWrapper.jl#L148-L169
Here we need 20 lines (plus a few lines here and there) so here efficiency is not questioned but it take many lines of code to write, test and maintain.

As we see with the ECOS example, not using bridges either adds a lot of code (c) or adds small inefficiencies that can only be resolved by careful analysis and adding complicated code (a) and b)).

So should bridges be used for such simple transformations ?

Suppose we have a bridge optimizer on top of an optimizer. When adding a bridge,

1. a copy of the function and set is stored in a model cache
2. functions and sets for the constraints generated by the transformation are computed

Both 1) and 2) are O(N) in terms of time and space where N is the number of terms in the function.
This is clearly less efficient than c) and it is also less efficient than a) and b) since only one copy is needed in a) and b) while the bridge needs two (one in 1) and one in 2)).

So at the moment, it seems that there is a compromise to be made when deciding whether to rely on bridges.
It simplify the solver wrapper but it will maybe not be as efficient and may prevent handling large problem that barely fit in memory.

However, as we will see below, these two copies can be eliminated and hence bridges can be made almost allocation free and hence there won't be any compromise anymore, a solver wrapper should only ever support a constraint that is supported natively.

1. The cache of the function and set before bridging is used to store the name and to implement MOI.get for MOI.ConstraintFunction and MOI.ConstraintSet. This removes the need from the bridge to implement the inverse transformation. However, in many bridges, the reverse transformation is not difficult to implement (this is the case for cases a), b) and c) above). Bridges implementing inverse transformation will be able to be used without a cache. In addition to the SingleBridgeOptimizer and LazyBridgeOptimizer, we could define two corresponding bridge optimizer that do not do any caching and use the bridge to retrieve the ConstraintFunction and ConstraintSet.
2. If we allow vector of terms to be AbstractVector instead of Vector, we could define MOIU.lazy_operate in addition to MOIU.operate and MOIU.operate! (see lazy_operate #526). MOIU.lazy_operate would apply the transformation lazily by not computing the new list of terms. For instance, we could do

struct LazyMap{T, VT <: AbstractVector{T}} <: AbstractVector{T}
    f::Function
    v::VT
end
function Base.iterate(lm::LazyMap, state = nothing)
    next = iterate(lm.v, state)
    lm.f(next[1]), next[2]
end
function lazy_operate(::typeof(-), ::Type{T}, f::MOI.ScalarAffineFunction{T})
    return MOI.ScalarAffineFunction(LazyMap(-, f.terms), -f.constant)
end

and that would allow to write a bridge between MOI.ScalarAffineFunction-in-GreaterThan and MOI.ScalarAffineFunction-in-LessThan that does not allocate.
There is one gotcha here. If a caching optimizer is used, since the bridges are applied on top of the caching optimizer, the caching optimizer receives the transformed constraints and it will collect the terms to store the function.
To avoid that we could apply the bridge below the caching optimizer, which would require the bridge optimizer to implement the allocate-load interface and will not work for copy-only solver that do not support the allocate-load interface.
I initially thought that implementing the allocate-load interface from the bridge optimizer would complicate the bridges too much and require the transformation to be done both in allocate and load which would be inefficient but for lazy bridge, the transformation is actually not done so it might actually make sense to implement the allocate-load from these bridges.

In summary, we would have 4 bridge optimizers:

	Caching	No caching
Bridge even if supported	SingleCachingBridgeOptimizer	SingleBridgeOptimizer
Only bridge if not supported	LazyCachingBridgeOptimizer	LazyBridgeOptimizer

The two current ones are in the first column, they will be renamed by adding Caching in the name.
Note that for bridge optimizers in the second column, we do not need to create an MOIU model anymore so no need for a @bridge macro with a list of (MOI.SingleVariable) ... () ... anymore.

And we would have 2 categories of bridges:

• Heavy bridges: Do not implement MOI.get for ConstraintFunction and ConstraintSet (i.e. inverse transformation) so need to be used with a caching bridge optimizer. Do not implement the allocate-load API so need to be used on top of a caching optimizer.
• Light bridges: Implement inverse transformation and the allocate-load API, use lazy_operate. It can be used with any bridge optimizer and can be used on either side of the caching optimizer but are more efficiently used with a non-caching bridge optimizer below the caching optimizer of without a caching optimizer.

In JuMP, we now have a LazyCachingBridgeOptimizer(BridgeOptimizer(optimizer)) which will be replaced by LazyCachingBridgeOptimizer(BridgeOptimizer(LazyBridgeOptimizer(optimizer))).
The inner bridge optimizer will contain all the light bridges and the outer one will contain all the heavy bridges.

Please use separate issues #525, #526 to talk about these specific changes if you have a comment that fit into these topics :)

• Require bridges to implement MOI.get for ConstraintFunction and ConstraintSet #713
• Implement Allocate-Load for AbstractBridgeOptimizer #720
• lazy_operate #526

[odow]

You had me at "When". I think lighter bridges are a fantastic way to head.

[mlubin]

Be careful opening up the bike shed for bridges, but yes, curious to hear your new ideas :)