From: Jesper Hansen <jesperh_at_skydebanen.net>

Date: Thu 02 Jan 2003 06:11:01 PM GMT

Message-ID: <3E1480B5.4090708@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 LyngbyReceived 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
*