Re: [Help-glpk] optimization problem

[xypron]

Hello Andrzej,


Bugzilla from address@hidden wrote:
> 
> Hello everybody.
> 
> Isn't it a problem of choice of bags from a list and simply checking
> whether 
> we have already chosen a bag with this color. For that you need a list
> object 
> with its operations and a set object with its operations.
> I am afraid that I see no purpose in using just LP for that task.
> 

Each bag contains multiple colors. The task is to cover the maximum number
of colors with a given number of bags. A greedy heuristic like choosing as
next 
bag the one with the most new colors does not guarantee an optimum solution.

Example:
Cover the maximum number of letters with 3 bags.

all sets:
abcde
fghi
fgj
hik
j

greedy heuristic:
abcde
fghi
hik

optimum:
abcde
fgj
hik

You can find a discussion of set covering problems here:
http://iris.gmu.edu/~khoffman/papers/set_covering.html

Best regards

Xypron

-- 
View this message in context: 
http://www.nabble.com/optimization-problem-tp22609378p22635680.html
Sent from the Gnu - GLPK - Help mailing list archive at Nabble.com.