Erwin Kalvelagen
2020-12-02 08:09:16
First a bit of theory. We can linearize
z = x*y
for binary variables x,y,z by:
z <= x
z <= y
z >= x+y-1
In your specific case, we can apply this as follows:
sum(i, z[i]) <= 100
z[i] >= x[i] + y[i] - 1
where z[i] is an extra binary variable. We don't need the <= constraints z[i] <= x[i], z[i] <= y[i]. We can relax z[i] to be continuous between 0 and 1 which sometimes can help a bit in performance.
Note that the presence of binary variables no longer makes this an LP, but rather this is a MIP model.