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