How to transform a big M into an SOS constraint in Gurobi?

[Mlika Zoubeir]

I have a constraint that is not linear of the form

 

a[k, k] * x[k] >= b * x[k] * (1 + sum(a[k1, k] * x[k1] for k1 in range(K))).

The variables are x[k] which are 0 or 1 for all k = 0, ..., K - 1. The input is K, a[k, n] and b.

 

If I use big M formulation, I can linearize it as

(a[k, k] * x[k] + M * (1 - x[k])) >= b * (1 + sum(a[k1, k] * x[k1] for k1 in range(K))),

but this is not useful in my case.

 

I would like to use SOS constraints to model this, how can I do this?     

[Tobias Achterberg]

Essentially, your constraint is a so-called indicator constraint. Namely, if
x[k] == 0, then the constraint is redundant. If x[k] == 1, then the constraint
is active and reads:

sum(b * a[k1,k] * x[k1] for k1 in range(K)) <= a[k,k] - b

Indicator constraints can be generally stated as

x = 1 -> a*y <= b

i.e., if a binary variable x is equal to 1 then some linear constraint should be
satisfied. Otherwise, the linear constraint may be violated.

Such indicator constraints can be modeled using an SOS1 condition as follows:
you introduce a new variable s >= 0 and add the linear constraint

a*y - s <= b

to the model. Choosing s > 0 allows to violate your original constraint. Now,
you just add the SOS1:

SOS1: (x,s)

to your model, which says that at most one of the variables can be non-zero.
Thus, if x = 1 it forces s = 0, and this means that your original constraint has
to be satisfied. On the other hand, if x = 0, then s can be arbitrarily large to
even out any violation of the original constraint.


Regards,

Tobias

[Enrique Fernández]

In general, is it better to use big M constraints or these SOS1 constraints?

(In terms of efficiency, numerical stability, etc..)

[Tobias Achterberg]

This is a very good question but hard to answer. The big-M formulation has the
tighter LP relaxation (which is good), because SOS1 constraints are not present
in the LP at all. But if the big-M is too large, then this is counter-productive
because it can significantly hurt the numerical properties of the LP relaxation,
slowing the LP solves down and making their solutions less accurate.

When given an SOS constraint, Gurobi's presolve will automatically convert it
into a big-M formulation if the required big-M's are "small enough". But note
that Gurobi can only calculate the big-M from the constraints and bounds given
in the model. If the user has problem knowledge that would allow for smaller
big-M's than those that can be mathematically proven (by simple domain
propagation steps) through the model formulation, then modeling the constraint
directly through big-M's might be beneficial.


Tobias

[Enrique Fernández]

Thanks for the detailed answer.

It seems like the bigM method is better if having domain knowledge that let's you specify the smallest possible M that works.

Thanks

[Pallenmar]

I can't seem to find the answer on other forums, but could you give some idea of how Gurobi solves the SOS1 constraints (or any of the other general constraints, I'm using the indicator constraints), if the big-Ms are not "small enough"? Does Gurobi solve these problems strictly logically rather than via relaxations? 

Thank you!

[Tobias Achterberg]

General constraints are translated into a set of new auxiliary (binary and/or
continuous) variables, linear constraints, and SOS constraints.

If the big-M's are not small enough to translate SOS constraints into linear
constraints, then the SOS constraints are dealt with by branching. Thus, they
are not added to the LP relaxation, and if the solution to the LP relaxation
violates an SOS constraint (e.g., there are two variables in an SOS1 constraint
with non-zero LP value), then this SOS constraint is a candidate for branching
(in addition to all integer variables with fractional LP value).

Branching on an SOS1 constraint means to split the variables of the SOS into two
sets: x[0],...,x[k-1] and x[k],...,x[n-1] such that in each set there is at
least one variable with non-zero LP value. Then, in one child node one fixes

x[0] = ... = x[k-1] = 0

and in the other child node one fixes

x[k] = ... = x[n-1] = 0.

For SOS2 constraints, the branching is similar, of course respecting the SOS2
structure.


Regards,

Tobias