Feature Request: Indicator Constraints

[sirwhinesalot]

Following up from my boolean modelling issue, one of the nicest features of Gurobi, CPLEX and SCIP are indicator constraints. They make modelling complex boolean constraints extremely easy, in fact Gurobi and CPLEX also include boolean AND and OR constraints which are just lovely, though those are not particularly hard to model once you have indicator constraints.

Indicator constraints can be implemented using Big-M, Convex Hull, or SOS constraints. The Big-M formulation is the simplest but variables need tight bounds for it to work nicely. Convex Hull needs less tight bounds and has better numerical properties but is more complicated and needs more additional variables and constraints. I have no idea how they are encoded with SOS constraints.

Are there any plans to expose the indicator constraint features of Gurobi? And if so, would they be replicated in Python-MIP for CBC by using one of the encoding tricks above?

[h-g-s]

Hi,

This would be a nice feature. We do not plan to implement Gurobi only features, so we would need to implement it in CBC. Do you have any reference on how implementing it ? Since we are adding SOS, this implementation seems to be interesting.

--

Haroldo Gambini Santos Computing Department Universidade Federal de Ouro Preto - UFOP email: haroldo@ufop.edu.br Haroldo.GambiniSantos@cs.kuleuven.be home/research page: www.decom.ufop.br/haroldo

It has long been an axiom of mine that the little things are infinitely the most important. -- Sir Arthur Conan Doyle, "A Case of Identity"

On Sat, 7 Sep 2019, César Santos wrote:

Following up from my boolean modelling issue, one of the nicest features of Gurobi, CPLEX and SCIP are indicator constraints. They make modelling complex boolean constraints extremely easy, in fact Gurobi and CPLEX also include boolean AND and OR constraints which are just lovely, though those are not particularly hard to model once you have indicator constraints.

Indicator constraints can be implemented using Big-M, Convex Hull, or SOS constraints. The Big-M formulation is the simplest but variables need tight bounds for it to work nicely. Convex Hull needs less tight bounds and has better numerical properties but is more complicated and needs more additional variables and constraints. I have no idea how they are encoded with SOS constraints.

Are there any plans to expose the indicator constraint features of Gurobi? And if so, would they be replicated in Python-MIP for CBC by using one of the encoding tricks above?

— You are receiving this because you are subscribed to this thread. Reply to this email directly, view it on GitHub, or mute thethread.[AB4VZOWH3QSGUZE6YGSA4PLQIQNS3A5CNFSM4IURLVU2YY3PNVWWK3TUL52HS4DFUVEXG43VMWVG G33NNVSW45C7NFSM4HJ7HKQA.gif]

[sirwhinesalot]

You have a formula of the form:

i -> (a x + b y <= c)

This is an indicator constraint, because i (a boolean variable) implies the rest.

There are 3 ways to implement this without some kind of built in support: Big-M, Convex Hull and SOS. The goal is to have the constraint "always succeed" when I is false (essentially turning it off)

Big-M:

a x + b y <= c + M(1 - i)

Where M should be the smallest number that makes this constraint always true when i is false. It can be calculated by getting the upper bound of (a x) + (b y) and subtracting c from it. This obviously requires all variables to be bounded, the tighter the better. For >= it's a similar idea but we care about the lower bound instead.

Convex Hull:

Unfortunately I'm still struggling to understand this one, so I'll have to leave it for now. I just know it has better numerical properties than Big-M and requires more constraints and auxiliary variables. This paper shows auxiliary variables are not strictly necessary, at least for binary variables: http://www.optimization-online.org/DB_FILE/2014/04/4309.pdf

SOS1:

For SOS1 I don't know how it is done at all, and cannot find information anywhere. The only advantages I see are that they should be more efficient then x + y + z <= 1 constraints and they can handle arbitrarily large variables rather than just booleans. If I figure it out I will inform you.

[h-g-s]

The paper "A Note on Linear On/Off Constraints" shows the case for bounded variables, which seems to be easy to implement. For the most general case it seems that a way more complicated approach is needed: "On handling indicator constraints in mixed integer programming" https://link.springer.com/article/10.1007/s10589-016-9847-8

[sirwhinesalot]

I would definitely stick with the simple implementation. Full support for indicator constraints, if it happens, should be at the CBC level and not Python-MIP.

[rodo-hf]

Hi, How is the current status on having indicator constraints? Because I am having such a problem at the moment. Would be nice to have an example code then.

[h-g-s]

Hi,

It is still in the TODO list. We are releasing soon CBC 3.0 (and a new python MIP version). We are currently running the latest tests with CBC to check if there are no regressions. After that I can go back to my TODO list.

--

Haroldo Gambini Santos Computing Department Universidade Federal de Ouro Preto - UFOP email: haroldo@ufop.edu.br Haroldo.GambiniSantos@cs.kuleuven.be home/research page: www.decom.ufop.br/haroldo

It has long been an axiom of mine that the little things are infinitely the most important. -- Sir Arthur Conan Doyle, "A Case of Identity"

On Wed, 11 Mar 2020, rodo-hf wrote:

Hi, How is the current status on having indicator constraints? Because I am having such a problem at the moment. Would be nice to have an example code then.

— You are receiving this because you commented. Reply to this email directly, view it on GitHub, orunsubscribe.[AB4VZOQ5GS55JKWFAUUBYT3RHAFSPA5CNFSM4IURLVU2YY3PNVWWK3TUL52HS4DFVREXG43VMVBW63LNMVXHJKTD N5WW2ZLOORPWSZGOEORWGPA.gif]

[rodo-hf]

Could someone please provide a little sample code for Big-M?

[sirwhinesalot]

There isn't really much to code, big-M is just an encoding trick. Lets say you have this constraint:

4x + 3y + 2z >= 2

You want to make this constraint conditional on some boolean variable, i.e, you want to model the following implication:

b -> 4x + 3y + 2z >= 2

(The above is an indicator constraint in MIP parlance) How do you encode an implication like the above in MIP? Well, if b is 0, then the constraint becomes irrelevant, i.e, we don't want it to actually constraint anything.

The simplest way to do it is as follows:

4x + 3y + 2z >= 2 -M*b

Where M is some "very large number", a big M so to say, e.g.

4x + 3y + 2z >= 2 -10000b

There you go, that's big M. If you want to model it in python-mip, we need to move that b back but that's no problem:

m += 4 * x + 3 * y + 2 * z + 10000 * b >= 2

If b is true and x, y and z have small bounds, this constraint will always work. There are two issues though:

1. What if x, y and z don't have small bounds? It might not properly disable the constraint then.
2. The bigger the M, the more the solver will struggle. If it is way too big, you'll get numerical errors.

This is why Gurobi and CPLEX have indicator constraints, they effectively compute good Ms for you. Until CBC decides this is an important thing to do, here's what can be done:

If the constraint is >=: For each variable in the constraint, if the weight is positive, multiply it by the variables lower bound. If the weight is negative, multiply it by the variable's upper bound. Sum all of that, and you have the minimal M for that one constraint.

This is the simplest possible way to get half-decent Ms. You really want to do some pre-solving where you minimize the Ms though, as Gurobi and CPLEX do, since that will give much better results by taking all constraints into account simultaneously (such that you have tighter bounds on every variable).

For <=, it is a bit more complicated, as the formula is:

4x + 3y + 2z <= 2 + M*(1-b)

So you have to do:

4x + 3y + 2z <= 2 + M - Mb 4x + 3y + 2z + Mb <= 2+M

[sirwhinesalot]

Just wanted to add some new information, SCIP explains how they implement indicator constraints using SOS1 constraints here: https://www.scipopt.org/doc-7.0.0/html/cons__indicator_8h.php

It's super simple:

z -> ax <= b

becomes:

ax - s <= b
s >= 0
sos1 z s

[h-g-s]

Hi @drlagos ! Yes, I recently noticed after watching a workshop that the implementation is simple indeed. We are now working to improve the cbc binaries, but this will be my next task !

[r-barnes]

Just checking in on this.

[rodo-hf]

Hi @h-g-s , is there any progress on that topic? Thanks