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

Question

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

但是如何创建新的约束？

想象一个简单的例子，我有 5 个城市，但是每个城市都没有道路，所以我想用新的限制来消除没有路段，我在 GLPK 中是怎么做的？

Answer 1

这是AMPL中 TSP 问题的示例（它是 Glpk 使用的 GNU MathProg 的超集），取自此处：

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