Monday, February 9, 2009

Set Covering Variant

> I need to model a variant of the set covering problem:
> we need to cover at least p% of the points.

The set covering problem looks like:

param a{I,J},binary;
var x{J},binary;

minimize cost: sum{j in J} x[j];
subject to covers{i in I}: sum{j in J} a[i,j]*x[j] >= 1;

We can formulate your problem with:

param a{I,J},binary;
param p >= 0, <= 1;
var x{J},binary;
var y{I} >= 0, <= 1;
minimize cost: sum{j in J} x[j];
subject to covers{i in I}: sum{j in J} a[i,j]*x[j] >= y[i];

subject to req: sum{i in I} y[i] >= p*card(I);

I believe y does not have to be binary and can be relaxed (between 0 and 1).