On Sun, Feb 8, 2009 at 9:02 PM, Yaron Kretchmer
<address@hidden> wrote:
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 ============================
_______________________________________________
Help-glpk mailing list
address@hidden
http://lists.gnu.org/mailman/listinfo/help-glpk