Monday, July 13, 2009

Formulation: sum{i in I} binvar[i]*intvar[i]<=C

> How to linearize sum{i in I} binvar[i]*intvar[i] ≤ C where binvar is a binary variable and intvar is an integer variable.

In general we can linearize y[i] = binvar[i]*intvar[i] as:

0 ≤ y[i] ≤ intvar.up[i]
y[i] ≤ binvar[i]*intvar.up[i]
y[i] ≤ intvar[i]
y[i] ≥ intvar[i] - intvar.up[i]*(1-binvar[i])

In this case we can drop the ≤ inequalities, so we have:

0 ≤ y[i] ≤ intvar.up[i]
y[i] ≥ intvar[i] - intvar.up[i]*(1-binvar[i])
sum{i in I} y[i] ≤ C