Generic bridges

Last time I wrote about bridges in JuMP and gave it a first try after reading about it and having a long phase of trial and error.

A couple of days later I wanted to add a new constraint type namely strictly less than and strictly greater than and realized that it's quite a bit of copy and paste with the current bridges. This is due to the fact that I definitely only want to support < directly and > should be bridged. It should also be bridged inside indicator and reified constraints though.

It's basically the same task as before just for another constraint type.

The idea this time is to have a generic approach and I got quite some help from Benoît Legat in this MOI issue that I have created.

Let me walk you through the steps involved and how it all works out nicely.

What do we want to support?

Last time we had this very specific bridge that transforms b => { x + y >= z} to b => { (-x) + (-y) <= -z}. This time we want to use a generic bridge that works for all inner constraints, or at least the ones we especially define. I think I mentioned the idea in the last post as well but wasn't sure how to accomplish that goal yet.

The general form of what we want to support is b => { not supported but bridgeable constraint }. This will make it very simple to support > constraints when we know how to support <. Maybe a new post about that constraint will be coming up next. Let me know whether you're interested 😉

Using another bridge in our parametric bridge

For accomplishing this goal we need to define a different kind of struct which gets parameterized with the inner bridge.

struct IndicatorBridge{T, B<:MOIBC.SetMapBridge{T}, A} <: MOIBC.AbstractBridge
    con_idx::CI
end

This means that we have a struct for every possible inner bridge that is a SetMapBridge (which is the case for our goal). Here the T stands for the type of the coefficients as usual. \(A\) is the activation condition so either active on one or on zero. For the user this is the difference between b => and !b =>.

Furthermore we again need to tell MOI that we support the constraint which can be done by defining a new MOI.supports_constraint method:

function MOI.supports_constraint(
    ::Type{<:IndicatorBridge{T, B}},
    ::Type{F},
    ::Type{<:MOI.IndicatorSet{A,S}}
) where {T, B, F<:MOI.VectorAffineFunction, A, S}
    is_supported = MOI.supports_constraint(B, MOIU.scalar_type(F), S)
    !is_supported && return false

    concrete_B = MOIBC.concrete_bridge_type(B, MOI.ScalarAffineFunction{T}, S)
    added_constraints = MOIB.added_constraint_types(concrete_B)
    length(added_constraints) > 1 && return false
    # The inner constraint should not create any variable (might have unexpected consequences)
    return isempty(MOIB.added_constrained_variable_types(concrete_B))
end

We give the type of the bridge as the first parameter as before and the function and set as the second parameter. The IndicatorSet is a parametric type itself which stores the activation condition as well as the type of the inner constraint.

First of all we need to make sure that we support the inner constraint we therefore use the bridge that is stored in our parametrized IndicatorBridge.

Afterwards we need to get the concrete bridge type concrete_B to make sure that we actually only add a single constraint in the bridge. This is important to make sure that we don't create any constraints outside the indicator constraint that we currently can't handle.

We additionally don't want to create new variables as this might have unexpected consequences.

Changes on how we add the bridge

Last time we had to just call add_bridge once to support our IndicatorBridge but now as it's parameterized by the inner constraint we need to define explicitly which inner constraints we want to support.

You might say: Oh I thought we support all of them... Isn't that the reason why we do this generic approach?

Well yeah that's true but I think it is still better to just have a single line than to copy ~100 and change some more stuff.

Now it's just something like:

MOIB.add_bridge(lbo, CS.IndicatorBridge{options.solution_type, MOIBC.GreaterToLessBridge{options.solution_type}})
MOIB.add_bridge(lbo, CS.IndicatorBridge{options.solution_type, CS.StrictlyGreaterToStrictlyLessBridge{options.solution_type}})

That isn't too bad I think.

All the bridge functions

Alright let's just implement the last couple of functions to make this work.

We call the concrete_bridge_type function before so let us start with that one:

function MOIBC.concrete_bridge_type(
    ::Type{<:IndicatorBridge{T,B}},
    G::Type{<:MOI.VectorAffineFunction},
    ::Type{IS},
) where {T,B,A,S,IS<:MOI.IndicatorSet{A,S}}
    concrete_B = MOIBC.concrete_bridge_type(B, MOI.ScalarAffineFunction{T}, S)
    return IndicatorBridge{T,concrete_B,A}
end

In this and the next two functions we more or less just return what the inner constraint returns. This means we call the same function for the inner constraint and then wrap some stuff around it. Here we call concrete_bridge_type and use the output as the bridge type of our IndicatorBridge.

The next two functions return which new constraint and variables are created by the bridge:

function MOIB.added_constraint_types(
    ::Type{<:IndicatorBridge{T,B,A}}
) where {T,B,A}
    added_constraints = MOIB.added_constraint_types(B)
    return [(MOI.VectorAffineFunction{T}, MOI.IndicatorSet{A,added_constraints[1][2]})]
end

function MOIB.added_constrained_variable_types(::Type{<:IndicatorBridge{T,B}}) where {T,B}
    return MOIB.added_constrained_variable_types(B)
end

We make sure that MOIB.added_constrained_variable_types(B) is empty beforehand but if we support that one day it might be helpful to just return what the inner constraint adds here.

For the new constraint we have to wrap it into our IndicatorSet this time. Here added_constraints[1][2] means we take the first constraint (we check before that we only have exactly one) and the [2] stands for the set whereas [1][1] would be the function of the constraint.

Last we need to tell MOI how the actual bridge works:

function MOIBC.bridge_constraint(::Type{<:IndicatorBridge{T, B, A}}, model, func, set) where {T, B, A}
    f = MOIU.eachscalar(func)
    new_func = MOIU.operate(vcat, T, f[1], MOIBC.map_function(B, f[2]))
    new_inner_set = MOIBC.map_set(B, set.set)
    new_set = MOI.IndicatorSet{A}(new_inner_set)
    return IndicatorBridge{T,B,A}(MOI.add_constraint(model, new_func, new_set))
end

For the function we need to concatenate the activation variable with the newly mapped function from the inner constraint. As we only allow flip sign bridges in our IndicatorBridge we can call the function MOIBC.map_function here.

The inner set is even easier as we don't have to combine anything here it will just be the inner constraint of our IndicatorSet.

Afterwards we put everything together as part of a MOI.add_constraint to get the constraint index (CI) that we need in our IndicatorBridge struct.

Conclusion

I hope you learned a bit more about bridges this time and have an idea on how to create more generic ones than last time. For the ConstraintSolver this was very much needed to support strictly less than / greater than constraints as well as anti pruning.

More about that maybe in another post if you're interested. 😉

Thanks everyone for reading and see you in the next couple of weeks!

If you enjoyed this post please consider supporting me and help me reach my goal of 20 patrons in 2021. 🎉

Feel free to continue with the next post on boolean constraints.

Special thanks to my 10 patrons!

Special special thanks to my >4$ patrons. The ones I thought couldn't be found 😄

• Site Wang

• Gurvesh Sanghera

• Szymon Bęczkowski

For a donation of a single dollar per month you get early access to these posts. Your support will increase the time I can spend on working on this blog.

There is also a special tier if you want to get some help for your own project. You can checkout my mentoring post if you're interested in that and feel free to write me an E-mail if you have questions: o.kroeger <at> opensourc.es

I'll keep you updated on Twitter OpenSourcES.

Want to be updated? Consider subscribing and receiving a mail whenever a new post comes out.

Enter your email

Powered by Buttondown.