Feature Request: Indicator Constraints about python-mip HOT 12 OPEN

from python-mip.

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.

from python-mip.

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

from python-mip.

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.

from python-mip.

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.

from python-mip.

from python-mip.

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

from python-mip.

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

from python-mip.

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

from python-mip.

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 !

from python-mip.

Just checking in on this.

from python-mip.

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

from python-mip.