[Help-glpk] The "good enough" set covering problem
From:
Yaron Kretchmer
Subject:
[Help-glpk] The "good enough" set covering problem
Date:
Sun, 8 Feb 2009 16:02:25 -0800
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;