Re: TSP formulation

Great model! Just to clarify:

Cities =.. [cities|Circuit],

sets

Cities = cities(Circuit), 

where Circuit is a list. Then I guess Cities[I] picks out the i'th argument in the term. 

Could you then explain what dist/3 does?

X is City1 for instance. Isn't City1 a variable or is it different when you use the "matrix" form Cities[I]?

Do you have any references to any comparison of CLP and MIP for TSP?

Thanks

Jesper

Mark Wallace wrote:

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

-- 
_______________________________________
Jesper Hansen         
Ph.D. student         
Telephone: (+45) 45 25 33 88 
Telefax.:  (+45) 45 25 26 73
E-mail: mailto:jha@imm.dtu.dk 
Homepage: http://www.imm.dtu.dk/~jha/
Department of Mathematical Modelling 
Building 305                      
Technical University of Denmark
DK-2800 Lyngby