Wondering if you knew any tricks off of the top of your head for this problem:
I have a model with a continuous decision variable x, indexed over a set: x_1, x_2, … x_n. x is nonnegative. I want to add a constraint which says that the number of positive entries in x is less than K. I can do it with Sum[…, AsInt[x[i] > 0]], but that is not a MIP constraint. Is there a standard trick I can use in this case?
I actually got this question two times this week. Answer:
Binary variable y(i);
parameter M(i) = x.up(i); (tight upper bound on x(i))
sum(i, y(i)) ≤ K;
x(i) ≤ y(i)*M(i);
Note that the we only have an implication one way: y(i)=0 => x(i)=0. In other words:
- if x(i)>0 => y(i)=1
- if x(i)=0 => y(i)=0 or 1
In the solution, the y(i)’s have no straightforward interpretation. We cannot just consider the y(i)’s as an indicator for (strictly)positive x(i)’s. If the inequality sum(i, y(i)) ≤ K is not tight, there may be y(i)’s equal to one while the corresponding x(i)=0.