使用MathProg定義集合包裝

Question

對於沒有經驗的人來說，這可能會非常混亂。

如何將the wikipedia article中的Set Packing問題定義爲MathProg程序，稍後在GLPK工具中運行？單獨

Intution將導致我弄成這個樣子：

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這是基於AMPL的一個子集），如下所示：

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。這是與代數公式唯一的區別。