Creation date: 2021-01-26

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.

Note

If you haven't read the previous post I highly suggest to start with that as there I explain the bridge system in general and some functions needed that I just reuse here and modify them slightly.

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.

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 😉

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.

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.

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.

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.

© Ole Kröger. Last modified: February 16, 2021. Website built with Franklin.jl.