# Encoding tsp_optimization.gringo

Name tsp_optimization.gringo [Root]    Graph Problems (32)    Hamilton (17) Martin Gebser Martin Gebser and Roland Kaminski A Gringo encoding of the Traveling Salesperson problem. The sum of edge costs is subject to minimization. 2009-03-10 13:18 2009-03-10 13:40 TravelingSalespersonSuite bound/1edge/2edgewt/3maxweight/1vtx/1 cycle/2 No ASP Contest 09 (Martin Gebser) % Select edges for the cycle 1 { cycle(X,Y) : edge(X,Y), cycle(X,Y) : edge(Y,X) } 1 :- vtx(X). 1 { cycle(X,Y) : edge(X,Y), cycle(X,Y) : edge(Y,X) } 1 :- vtx(Y). reached(X) :- bound(X). reached(Y) :- reached(X), cycle(X,Y). :- vtx(X), not reached(X). cost(X,Y,C) :- edgewt(X,Y,C). cost(X,Y,C) :- edgewt(Y,X,C), { edgewt(X,Y,D) : edgewt(X,Y,D) } 0. % Weight constraint on the Hamiltonian cycle :- W+1 [ cycle(X,Y) : cost(X,Y,C) = C ], maxweight(W). % Symmetry breaking: Reach "smaller" neighbor from starting node % (assumes symmetric costs for both directions of an edge!) :- bound(X), cycle(Y,X), cycle(X,Z), Y < Z. #minimize [ cycle(X,Y) : cost(X,Y,C) = C ]. #hide. #show cycle(X,Y).