Multiplying two variables in a constraint: one is integer and the other is binary

[Mateo Romero-Amich Alonso]

I have to solve an optimization problem using java-gurobi and one of the constraints is like: X[i] <= M[i]*Y[i] 

where X and M are integer variables and Y binary 

I´m not able to find a solution in linear expressions to do it. Even if I try GRBQuadExpr the program tells me that Y cannot be resolved as a variable. 

Does anyone know how to do it? thankss 

[Tobias Achterberg]

You can use indicator constraints as follows:

Y[i] = 0 -> X[i] <= 0
Y[i] = 1 -> X[i] <= M[i]

See the "General Constraints" section at
http://www.gurobi.com/documentation/7.5/refman/constraints.html and
http://www.gurobi.com/documentation/7.5/refman/py_model_addgenconstrindic.html

Assuming that the M variables are non-negative, you can also use

Y[i] = 0 -> X[i] <= 0

X[i] <= M[i]

because then the second inequality is also valid even if Y[i] = 0 (so you don't need to
use an indicator constraint here).

This second formulation can also be modeled as follows:

X[i] <= M[i]

Y[i] + Z[i] = 1
SOS1(X[i], Z[i])

The second constraints introduces the complement of Y[i]; we call it Z[i]. The SOS1
constraint says that at most one of the members in the set can be non-zero. This means
that if Z[i] = 1 (i.e., Y[i] = 0) then X[i] is forced to be 0.
See http://www.gurobi.com/documentation/7.5/refman/py_model_addsos.html

If you have finite upper bounds on the X variables like this:

X[i] <= UX[i]

with UX being arrays of constants (and again, the M variables are non-negative), then you
can model this just with linear constraints:

X[i] <= M[i]

X[i] <= UX[i] * Y[i]

The first constraint is as above. In the second constraint you can see that if Y[i] = 0
then X[i] is forced to be zero as well. On the other hand, if Y[i] = 1, then the
constraint is redundant because X[i] <= UX[i] is already true due to the upper bound of
X[i]. This second constraint is a so-called "big-M constraint". If UX[i] is pretty large,
then this is usually a source of numerical issues, and the SOS1 formulation above is to be
prefered.

Note that the indicator formulation will automatically be translated into an SOS1 or a
"big-M" formulation, depending on the magnitude of the upper bound of X[i]. So, in
general, the indicator formulation should do the right thing for you.


Best regards,

Tobias