如何使用GLPK在TSP中創建新的約束條件

Question

我使用此示例TSP來計算巡視。

但是如何創建新的約束呢？想象一個簡單的例子，我有5個城市，但每個城市都沒有公路，所以我想消除沒有新的限制的路段，我如何在GLPK中做到這一點？

Answer 1

下面是AMPL一個TSP問題（這是GLPK使用GNU MathProg的超集），從here採取的例子：

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);