Re: TSP formulation

Hi Jesper,
It isn't the most efficient formulation, but it is expressible in ECLiPSe, viz:

:- lib(ic), lib(ic_global), lib(propia), lib(branch_and_bound).

tsp(N,List,Cost) :-
   init_cities(N,List),
   constrain_dists(N,List,Dists),
   search_min(List,Dists,Cost).

init_cities(N,List) :-
   length(List,N),
   M is N-1,
   List::0..M,
   ic:alldifferent(List).

constrain_dists(N,List,Dists) :-
   List = [Home|_],
   append(List,[Home],Circuit),
   Cities =.. [cities|Circuit],
   ( for(I,1,N),
     foreach(Dist,Dists),
     param(Cities)
   do
     dist(Cities[I],Cities[I+1],Dist)
   ).

dist(City1,City2,D) :-
   X is City1,
   Y is City2,    
   ( c(X,Y,D) ; c(Y,X,D) ) infers ac.


search_min(List,Dists,Cost) :- 
   Cost #= sum(Dists),
   minimize(labeling(List), Cost).

%%%%%%%%%   Testing   %%%%%%%%%%%%

% Data
 
c(0,1,30).
c(0,2,60).
c(0,3,41).
c(0,4,17).
c(0,5,70).
c(1,2,58).
c(1,3,46).
c(1,4,46).
c(1,5,48).
c(2,3,21).
c(2,4,59).
c(2,5,40).
c(3,4,38).
c(3,5,50).
c(4,5,78).

% Goal
test(List,Cost) :-
    tsp(6, List, Cost).
-- 
_______________________________________________________________
Dr. Mark Wallace, IC-Parc,		Phone  +44 (0)20 7594 8434 
William Penney Laboratory, 		Fax    +44 (0)20 7594 8432
Imperial College, London SW7 2AZ, UK.	Email: mgw@icparc.ic.ac.uk