# Encoding nontight-tsp.lparse

Name nontight-tsp.lparse [Root]    Graph Problems (32)    Hamilton (17) Martin Gebser Lengning Liu and Miroslaw Truszczynski Authors: Lengning Liu and Miroslaw Truszczynski Affiliation: University of Kentucky Email: {lliu1, mirek}@cs.uky.edu 2009-03-30 13:03 2009-03-10 13:04 TravelingSalespersonSuite bound/1edge/2edgewt/3maxweight/1vtx/1 hc/2 No uedge(X,Y) :- edge(X,Y). uedge(Y,X) :- edge(X,Y). % Select edges for the cycle { dhc(X,Y) } :- uedge(X,Y). % Each vertex has at most one incoming edge in a cycle :- 2 { dhc(X,Y):uedge(X,Y) }, vtx(Y). % Each vertex has at most one outgoing edge in a cycle :- 2 { dhc(X,Y):uedge(X,Y) }, vtx(X). % Every vertex must be reachable from the initial vertex through chosen % hc(v,u) edges :- vtx(X), not r(X). r(Y) :- dhc(X,Y), uedge(X,Y), initialvtx(X). r(Y) :- dhc(X,Y), uedge(X,Y), r(X), not initialvtx(X). initialvtx(1). % Compute "hc" hc(X,Y) :- dhc(X,Y), edge(X,Y). hc(X,Y) :- dhc(Y,X), edge(X,Y). % Weight constraint on the H. cycle % :- W+1 [ hc(X,Y) : vtx(X;Y) = weight(edgewt(X,Y)) ], maxweight(W). :- W+1 [ hc(X,Y) : edgewt(X,Y,WE) : vtx(X;Y) = WE ], maxweight(W).