如何使用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);