1

経験のない人にとって、これは非常に混乱する可能性があります。

ウィキペディアの記事にあるセット パッキング問題を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;

しかし、その論理は明らかに間違っており、私はそれを終わらせることさえできません.

4

1 に答える 1

0

次のように、 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

于 2015-11-29T15:53:28.010 に答える