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