GLPK Mathprog集群

Question

我正在编写一个模型，该模型可以解决涉及尺寸、需求和多重选择约束的背包问题( 这里，参见图8和9)。您可以找到基本背包问题这里的GMPL模型示例。对于任何想要快速解释背包问题的人，请阅读以下说明：

你是个冒险家，偶然发现了一个宝藏。有数以百计的精彩项目'i‘，每一个有一个重量'w’和一个利润'p‘。假设你有一个背包，它的重量相当于“c”，你想在不把背包装满太多的情况下获得最大的利润。什么是最好的组合项目，这样你才能获得最大的利润？

代码：

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

其中'I‘是条目篮，xi是二进制变量(0 =未选择，1=选择)

我遇到的问题是增加了多个组。MCKP要求从每个组中选择一个项目。例如，假设我们有三个组可供选择。它们可以表示如下(忽略实际值)：

# 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;

对于如何迭代每个组，以及如何定义变量x，我感到困惑。

var x{i,j} binary;

其中I是组j中项的索引。这假设我定义了一组集合：

set Groups{ONE,TWO,THREE}

然后，我将遍历一组项目：

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

但我很担心，因为我认为GMPL不支持有序集。我已经看到了与这相关的问题，答案建议在集合中定义一个集合。然而，我不知道它将如何适用于这一特定情况。

我的主要问题是:在GMPL中，我如何迭代一组集合(在本例中是一组组，其中每个组都有一组项)？

Answer 1

与安普尔不同，GMPL不支持一组集合。下面是如何在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;

如果您的变量不超过300个，则可以使用AMPL免费学生版和求解器(例如CPLEX或Gurobi)。

Answer 2

基于这个gnu邮件列表线程，我相信GMPL/MathProg支持您想要做的事情。下面是他们的例子：

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;

在您的示例中，我假设您将使用类似于@vitaut答案中的数据块的set Items{1..3}, within Groups;。