Re: [Help-glpk] optimization problem

[xypron]

Hello,


rsymbx wrote:
> 
> My question:
> First of all, is this even a problem that's appropriate for linear
> programming? ... I'd appreciate some suggestions on how to model 
> the problem such that GLPK doesn't complain.
> 

see model below.

Best regards

Xypron



/* Problem posed by rsymbx

1) Tom is given a large box which contains 1000 bags of marbles.
2) Inside each bag, there are between 1 and 50 marbles.
3) Within a given bag, there are no duplicate colors of marbles, 
   however there are duplicate colors of marbles across the bags.
4) The bags are labeled and Tom has a list of what color marbles 
   each bag contains.

Objective:
Tom wants to collect as many UNIQUE colors of marbles as 
possible, but is only allowed to pick out 100 bags from the box.
Tom derives absolutely no value from getting duplicate colors of 
marbles. Tell Tom which 100 bags to pick.
*/

set Bags   := {1..1000};
set Colors := {1..10000};

# To keep things easy let us create random bags.
param ncol{b in Bags} := 5 + 30 * Uniform(0,1);
set Bag{b in Bags} := 
  setof{ c in Colors : Uniform(0,1) < ncol[b]/card(Colors) } c;

# Do a little analytics
set maxBag := setof{ b in Bags : forall{n in Bags} card(Bag[b]) >=
card(Bag[n])} card(Bag[b]);
set minBag := setof{ b in Bags : forall{n in Bags} card(Bag[b]) <=
card(Bag[n])} card(Bag[b]);
set allCol := setof{ b in Bags, c in Bag[b]} c;
printf "The smallest bag contains %d marbles\n", sum{n in minBag} n;
printf "The largest bag contains %d marbles\n", sum{n in maxBag} n;
printf "%d colors are used\n", card(allCol);

# Bag b is chosen
var x{b in Bags}, binary;
# Color c is in a chosen bag
var y{c in Colors}, >=0, <=1;

# objective
maximize obj :
  sum{c in Colors} y[c];

# maximum of 50 bags
s.t. nBags :
  sum{b in Bags} x[b] <= 50;
# count only colors that are in a chose bag
s.t. fCol{c in Colors} :
  y[c] <= sum{b in Bags : c in Bag[b]} x[b];

solve;

printf "Bags chosen:\n";
for {b in Bags : x[b] > 0}
  printf "Bag %4d, ", b;
printf "\n";
printf "Colors retrieved: %d\n", sum{c in Colors} y[c];

end;

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