Re: TSP formulation

From: Jesper Hansen <jesperh_at_skydebanen.net>
Date: Thu 02 Jan 2003 06:11:01 PM GMT
Message-ID: <3E1480B5.4090708@skydebanen.net>
```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
```
Received on Thu Jan 02 17:20:44 2003

This archive was generated by hypermail 2.1.8 : Wed 16 Nov 2005 06:07:20 PM GMT GMT