この例のTSPを使用して、ツアーを計算しました。
しかし、新しい制約を作成するにはどうすればよいでしょうか?
簡単な例を想像してみてください。私は 5 つの都市を持っていますが、すべての都市に道路がないため、新しい制限のある道路セクションなしで削除したいのですが、GLPK でどのように行うのですか?
AMPL (Glpk で使用される GNU MathProg のスーパーセット) での TSP 問題の例を次に示します。
set S ordered;
param n := card {S};
set SS := 0 .. (2**n - 1);
set POW {k in SS} := {i in S: (k div 2**(ord(i)-1)) mod 2 = 1};
set LINKS := {i in S, j in S: ord(i) < ord(j)};
param cost {LINKS} >= 0;
var X {LINKS} binary;
minimize TotCost: sum {(i,j) in LINKS} cost[i,j] * X[i,j];
subj to Tour {i in S}:
sum {(i,j) in LINKS} X[i,j] + sum {(j,i) in LINKS} X[j,i] = 2;
subj to SubtourElim {k in SS diff {0,2**n-1}}:
sum {i in POW[k], j in S diff POW[k]: (i,j) in LINKS} X[i,j] +
sum {i in POW[k], j in S diff POW[k]: (j,i) in LINKS} X[j,i] >= 2;
data;
set S := a b c d ;
param cost: a b c d :=
a . 43 21 19
b . . 21 12
c . . . 39
d . . . . ;
すべての都市間にリンクがない場合は、LINKS
セット内の既存のリンクのみを提供することでモデル化できます。次に例を示します。
# model:
set LINKS;
# data:
set LINKS := (a b) (b d);