1

在尝试解决一个相当大的 TSP 问题时,我在计算 Mathprog 中的链接节点时遇到了麻烦:假设我有

set C  := 0..645;  #  a set of nodes
set A  := {i in  C, j in  C: i!=j};  # a set of edges

距离函数 d(c1,c2)

var a{(i,j) in A}, binary;  # binary variables that mean "go through edge i-j"
minimize walk: sum{(i,j) in A} d[i,j] * a[i,j];  # an objective function

和其他一些条件

subject to get_out {i in C}: sum{(i,j) in A} a[i,j] = 1; 
subject to get_in  {j in C}: sum{(i,j) in A} a[i,j] = 1;

进行所有可能的削减以解决电路需要电源组和其他一些东西,但是在 20 多个节点上,问题太贪婪了,我无法找到解决方案。

所以我想我会限制求解器连接所有 a[i,j] 强加

 a[i,j], a[j,k], a[k,w], ..., a[z,i] =1 with i!= {j,k,w,...,z} and j!={k,w,...,z} and ...

这与

 check(a[i,C]) {
   while C is empty 
     take j: a[i,j]=1;
     check( a[j,{C diff {i}}] ) 
 }

这可能不会导致解决方案,但无法实现如此简单的事情令人非常沮丧......有没有办法在 mathprog (gmpl) 中实现这样的伪代码?

4

0 回答 0