Indicator constraints with multiple binary variables

[yxzhan...@gmail.com]

In my model, I used several binary variables associated with Big M, however, the user manual and provided example in Gurobi only consider one binary variables.

The form of the constraints with multiple binary variables is like this:

M(1 - x) + M(1 - y) + Supply - Demand >= 10.

when both "x" and "y" equal to 1, the constraint is valid, otherwise, the constraint is redundant.

I wonder how to model this constraint using indicator constraint of Gurobi 7.0.1, or if there are other ways to eliminate the

negative influence of Big M. Thanks!

[Daniel Espinoza]

Hi Yongxiang

One way is to define z = AND(x,y) and then use z for the indicator constraint.

Hope this helps

Daniel

[Michael Winkler]

 You can add another binary variables and link this one to these two that should trigger the supply-demand constraint.

E.g., you add another binary z and

x + y - z <= 1
z = 1 => Supply - Demand >= 10

Cheers,
Michael

[Yongxiang Zhang]

Hi Daniel,

I understand your transformation method, however, I want to ask whether the proposed general constraints method is faster than Big M method ? Have you make any tests on those two methods ?

Thanks for your reply,

Yongxiang Zhang

[Yongxiang Zhang]

Hi Michael,

Your formulation indicates that if "x = 1 and y = 0" or "x = 0 and y = 1", then the variable "z" can be 1 or 0.

However in the original Big M formulation, if "x = 1 and y = 0" or "x = 0 and y = 1", then the constraint will be redundant, which means the variable "z" will be 0.

So I think your method may be slower than the original Big M formulation.

Thanks for your reply,

Yongxiang Zhang

[Michael Winkler]

This is hard to answer, what is in the end faster. Usually we will transform indicator into SOS or Big M internally. If you yourself use a huge Big M then it might lead to numerical problem or violated solution while the SOS transformation is more stable in terms of numerics.
In the end you should test what works best on your model.

Cheers, Michael

[Michael Winkler]

You can install an objective value on z to make sure that these solutions are avoided. Note that in your Big M formulation it can also happen that even if x + y <= 1 still Supply - Demand >= 10 is fulfilled. But I guess due to the objective function this is an unlikely solution and there exists a better solution where this constraint is violated. This is similar even with the introduction of z and the linear constraint I added.

Cheers,
Michael

[Yongxiang Zhang]

Hi Michael,

As far as I am concerned, numerical problem is not so good for the model. 

I will make some tests on my model and I will inform you the results later on. 

Thanks for your reply,

Yongxiang Zhang