Monday, August 9, 2010

OR in MIP

Question: If we have two non-negative variables, X1, X2 >= 0 and we know at least one of them is zero. How shall we linearize the constraints? In other word, the constraints are:
X1>= 0
X2 >=0
X1*X2 = 0.

The details are very much problem dependent, but

x1*x2 =0

can be formulated as

x1 <= 0 OR  X2 <= 0

i.e.

x1 <= M1*b
x2 <= M2*(1-b)
b in {0,1}
M1 = (tight) upper bound on X1 (constant)
M2 = (tight) upper bound on X2 (constant)