Wednesday, January 20, 2010

Counting positive variables

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.