GLPK Mathprog group of sets

Question

I'm trying to code a model that can solve the Multiple Choice Knapsack Problem (MCKP) as described in Knapsack Problems involving dimensions, demands and multiple choice constraints: generalization and transformations between formulations (Found here, see figures 8 an 9). You can find an example GMPL model of the basic knapsack problem here. For anyone looking for a quick explanation of the knapsack problem read the following illustration:

You are an adventurer and have stumbled upon a treasure trove. There are hundreds of wonderful items 'i' that each have a weight 'w' and a profit 'p'. Say you have a knapsack with weight capacity as 'c' and you want to make the most profit without overfilling your knapsack. What is the best combination of items such that you make the most profit?

In code:

maximize obj :
sum{(i,w,p) in I} p*x[i];

Where 'I' is the basket of items, and x[i] is the binary variable (0 = not chosen, 1 = chosen)

The problem that I am having trouble with is the addition of multiple groups. MCKP requires exactly one item to be selected from each group. So, for example, lets say we have three groups from which to choose. They could be represented as follows (ignore actual values):

# Items: index, weight, profit
set ONE :=
1 10 10
2 10 10
3 15 15
4 20 20
5 20 20
6 24 24
7 24 24
8 50 50;

# Items: index, weight, profit
set TWO :=
1 10 10
2 10 10
3 15 15
4 20 20
5 20 20
6 24 24
7 24 24
8 50 50;

# Items: index, weight, profit
set THREE :=
1 10 10
2 10 10
3 15 15
4 20 20
5 20 20
6 24 24
7 24 24
8 50 50;

I am confused on how I can iterate over each group and how I would define the variable x. I assume it would look something like:

var x{i,j} binary;

Where i is the index of items in j of groups. This assumes I define a set of sets:

set Groups{ONE,TWO,THREE}

Then I'd iterate over the groups of items:

sum{j in Groups, (i,w,p) in Groups[j]} p*x[i,j];

But I am concerned because I believe GMPL does not support ordered sets. I have seen this related question where the answer suggests defining a set within a set. However, I am not sure how it would apply in this particular scenario.

My main question, to be clear: In GMPL, how can I iterate over sets of sets (in this case a set of groups where each group has a set of items)?

Answer 1

Unlike AMPL, GMPL doesn't support sets of sets. Here's how to do it in AMPL:

set Groups;
set Items{Groups} dimen 3;

# define x and additional constraints
# ...

maximize obj: sum{g in Groups, (i,w,p) in Items[g]} p*x[i];

data;

set Groups := ONE TWO THREE;

# Items: index, weight, profit
set Items[ONE] :=
1 10 10
2 10 10
3 15 15
4 20 20
5 20 20
6 24 24
7 24 24
8 50 50;

# Items: index, weight, profit
set Items[TWO] :=
1 10 10
2 10 10
3 15 15
4 20 20
5 20 20
6 24 24
7 24 24
8 50 50;

# Items: index, weight, profit
set Items[THREE] :=
1 10 10
2 10 10
3 15 15
4 20 20
5 20 20
6 24 24
7 24 24
8 50 50;

If you have no more than 300 variables, you can use a free student version of AMPL and solvers (e.g. CPLEX or Gurobi).

Answer 2

Based on this gnu mailing list thread, I believe GMPL/MathProg has support for what you want to do. Here's their example:

set WORKERS;
param number_of_shifts, integer, >= 1;
set WORKER_CLIQUE{1..number_of_shifts}, within WORKERS;

data;
set WORKERS := Jack Kate Sawyer Sun Juliet Richard Desmond Hugo;
param number_of_shifts := 2;
set WORKER_CLIQUE[1] := Sawyer, Juliet;
set WORKER_CLIQUE[2] := Jack, Kate, Hugo;

In your example, I assume you'd use something like, set Items{1..3}, within Groups; with the data block from @vitaut's answer.