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

[Andrew Makhorin]

> I have a problem to solve at work  which at best can be described as a
> "good enough" set covering problem. I #39;m appreciate the forum #39;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).

Please note that your problem may be hard for glpk due to its size.

>  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.

You need to relax the covering constraints. For example:

   s.t. covers{m in Ys}: sum{r in Z} A[r,m]*Route[r] >= z[m];
   s.t. foo: sum{m in Ys}: z[m] >= percentage * card(Ys);

where z[m] is a binary variable: z[m] = 1, if set m is covered, and 0
otherwise.

> *) 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? (^_^) )