使用MathProg定义集合包装

Question

对于一个没有经验的人来说，这是非常令人困惑的。

如何将维基百科文章中的集合打包问题定义为MathProg程序，以便稍后在GLPK工具中运行？

光凭直觉就会让我陷入这样的境地：

var x

maximize SetPacking :
 sum {s in Subsets} x
s.t.         ??              //x is an integer 0 or 1
s.t.         ??              //amount of x <=1
end;

但它的逻辑显然是错误的，我甚至无法完成它。

Answer 1

您可以将安普尔 (和基于AMPL子集的MathProg )中的集合包装问题表述如下：

set U; # universe
set S; # subsets
set Members{S}; # members of subsets

# every set is either in the set packing or not
var x{S} binary;

# maximize the total number of subsets
maximize NumSets: sum{s in S} x[s];

# selected sets have to be pairwise disjoint
s.t. Disjoint{e in U}: sum{s in S: e in Members[s]} x[s] <= 1;

注意，您必须引入索引集Members，每个元素Members[s]都表示子集s的成员。这是唯一与代数公式不同的地方。