Re: [Help-glpk] optimization problem

[Andrzej Mazurkiewicz]

Thanks for Xypron for the explanation.

I have understood that there in one bag there are marbles of one color only.

Thanks once again.
Regards
Andrzej Mazurkiewicz


Saturday 21 of March 2009 13:48:40 xypron napisał(a):
> 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