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

[Oscar Peredo]

Hi,
in the context of crew scheduling optimization (in which the set covering problem naturally appears and represents the hardest part of the whole problem) the option --mostf seems to work fine in some instances because it realices the branching in the "most fractional variable". The idea behind it is to fill the cells of the set with 1's as soon as posible to obtain a feasible solution in a reasonable time (the quality of that solution is another story...). 

Saludos!

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