Encoding tsp_optimization.gringo

Name	tsp_optimization.gringo
Class Tree	[Root] Graph Problems (32) Hamilton (17) TravelingSalespersonSuite (5)
Submitter	Martin Gebser
Author	Martin Gebser and Roland Kaminski
Description	A Gringo encoding of the Traveling Salesperson problem. The sum of edge costs is subject to minimization.
Created	2009-03-10 13:18
Modified	2009-03-10 13:40
Languages	Gringo 2.0.2
Language Features	Cardinality constraints Optimization Choice rules Weight constraints
Compatible Instance Classes	TravelingSalespersonSuite
Input Predicates	bound/1 edge/2 edgewt/3 maxweight/1 vtx/1
Output Predicates	cycle/2
Encoding Parameter
Standalone	No
Tags	ASP Contest 09 (Martin Gebser)
Attributes
Content	% 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).

Actions