[Help-glpk] The "good enough" set covering problem

[Yaron Kretchmer]

Hi All
I have a problem to solve at work  which at best can be described as a "good enough" set covering problem. I'm appreciate the forum's advice on how to tackle it. Coming from an engineering background, my nomenclature may be deficient- my apologies for that. 

So here goes:
*) As with a "regular" set covering problem, I have a large domain ( up to 600K elements) which should be covered by a small set of groups (out of a maximum of about 1000 different groups). The "good enough" part is that it is not mandatory to cover the entire domain - we just need to cover "most" of the domain ("most" is defined as a percentage of the number of elements in the domain, and given as a parameter to the problem). 
*) I came up with a formulation of the classic set covering problem (enclosed) , but am struggling on how to convert it to a "good enough" covering problem.
*) Also, what command-line options are recommended for solving set covering problems? Are there any gotchas I should be aware of (except for set covering being NP complete? (^_^) )


Thanks for your time
Kretch


================= Begin Set Covering ============================

set Z;
set Ys;
param A{r in Z, m in Ys}, binary;
var Route{r in Z}, binary;
minimize cost: sum{r in Z} Route[r];
subject to  covers{m in Ys}: sum{r in Z} A[r,m]*Route[r]>=1;

data;
set Z:=  Z1 Z2 Z3 Z4 Z5 Z6 Z7 Z8 Z9 Z10;
set Ys:=  Y1 Y2 Y3 Y4 Y5 Y6 Y7 Y8 Y9 Y10 Y11 Y12 Y13 Y14 Y15 Y16 Y17 Y18 Y19 Y20;
param A :  Y1 Y2 Y3 Y4 Y5 Y6 Y7 Y8 Y9 Y10 Y11 Y12 Y13 Y14 Y15 Y16 Y17 Y18 Y19 Y20 := 
Z1  0 1 0 0 0 0 0 0 0 0 0 0 1 0 1 0 1 1 0 0
Z2  0 0 0 0 0 1 0 0 0 0 1 0 0 0 0 0 1 0 0 1
Z3  0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
Z4  0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 1
Z5  0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 1 0 1 0 0
Z6  0 0 0 0 0 0 0 0 1 0 0 0 0 1 0 0 0 0 0 1
Z7  0 1 0 0 0 0 0 0 0 1 0 0 0 0 0 0 1 0 0 1
Z8  0 0 1 0 0 0 1 0 0 0 0 0 0 0 0 1 0 0 1 0
Z9  1 0 1 1 1 0 0 1 0 0 1 1 0 0 0 0 0 0 0 0
Z10 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 0 0
;


end;



================= End Set Covering   ============================