使用 MathProg 定义集合打包
Defining Set Packing using MathProg
对于零经验的人来说,这可能会让人感到困惑。
如何将 the wikipedia article 中看到的 Set Packing 问题定义为 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;
但是它的逻辑明显是错误的,我根本看不完
您可以在 AMPL(以及基于 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
的成员。这是与代数公式的唯一区别。
对于零经验的人来说,这可能会让人感到困惑。
如何将 the wikipedia article 中看到的 Set Packing 问题定义为 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;
但是它的逻辑明显是错误的,我根本看不完
您可以在 AMPL(以及基于 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
的成员。这是与代数公式的唯一区别。