Определение набора упаковки с помощью MathProg

Question

Для кого-то с нулевым опытом это может быть очень запутанным.

Как определить проблему 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;

Но его логика явно неверна, и я даже не могу закончить это.

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, Это единственное отличие от алгебраической формулировки.