/*********************************************************** tsp_mip.pi from Constraint Solving and Planning with Picat, Springer by Neng-Fa Zhou, Hakan Kjellerstrand, and Jonathan Fruhman ***********************************************************/ import mip. main => M = {{0,6,1,5,0,0}, % cost matrix {6,0,5,0,3,0}, {1,5,0,5,6,4}, {5,0,5,0,0,2}, {0,3,6,0,0,6}, {0,0,4,2,6,0}}, tsp(M). tsp(M) => N = length(M), NextArr = new_array(N,N), NextArr :: 0..1, foreach (I in 1..N, J in 1..N) if M[I,J] == 0 then NextArr[I,J] = 0 end end, % each vertex is followed by exactly one vertex in a tour foreach (I in 1..N) sum([NextArr[I,J] : J in 1..N]) #= 1 end, % each vertex is preceded by exactly one vertex in a tour foreach (J in 1..N) sum([NextArr[I,J] : I in 1..N]) #= 1 end, % no sub-tours OrderArr = new_array(N), OrderArr :: 1..N, OrderArr[1] = 1, % visit vertex 1 first % linear ordering constraints foreach (I in 2..N, J in 2..N, I !== J) OrderArr[I] - OrderArr[J] + NextArr[I,J]*N #=< N-1 end, TotalCost #= sum([NextArr[I,J]*M[I,J] : I in 1..N, J in 1..N, I !== J]), solve($[min(TotalCost)], NextArr), foreach (I in 1..N, J in 1..N) if NextArr[I,J]==1 then printf("%w -> %w\n",I,J) end end, println(cost=TotalCost).