2

我正在尝试编写一个可以解决多项选择背包问题 (MCKP) 的模型，如涉及维度、需求和多项选择约束的背包问题中所述：公式之间的泛化和转换（在此处找到，参见图 8 和图 9）。您可以在此处找到基本背包问题的示例 GPL 模型。对于寻求快速解释背包问题的任何人，请阅读以下插图：

你是一个冒险家，偶然发现了一个宝库。有数百个美妙的项目“i”，每个都有一个重量“w”和一个利润“p”。假设您有一个重量为“c”的背包，并且您想在不使背包装满的情况下获得最大的利润。使您获得最大利润的项目的最佳组合是什么？

在代码中：

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

其中“I”是一篮子物品，x[i] 是二元变量（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];

但我很担心，因为我相信 GPL 不支持有序集。我已经看到了这个相关的问题，其中答案建议在集合中定义一个集合。但是，我不确定它在这种特定情况下如何应用。

我的主要问题要明确：在 GPL 中，我如何迭代集合（在这种情况下是一组组，其中每个组都有一组项目）？

4

2 回答 2

2

与AMPL不同，GPL不支持集合集。以下是在 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）。

于 2013-05-02T04:06:03.887 回答
2

基于这个gnu 邮件列表线程，我相信 GPL/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;

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

于 2017-04-11T17:29:18.667 回答