如何使用GLPK在TSP中创建新的约束

Question

我使用了这个示例TSP来计算行程。

但是如何创建新的约束呢？

想象一个简单的例子，我有5个城市，但是每个城市都没有道路，所以我想消除没有新限制的路段，我如何在GLPK中做到这一点？

Answer 1

下面是AMPL (Glpk使用的GNU MathProg的超集)中的一个TSP问题的示例，取自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);