Encoding tight-tsp.lparse

Name tight-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:01 TravelingSalespersonSuite bound/1edge/2edgewt/3maxweight/1vtx/1 hc/2 No % Define the permutation 1 { perm(I,X) : vtx(I) } 1 :- vtx(X). 1 { perm(I,X) : vtx(X) } 1 :- vtx(I). % Two consequtive vertices in the permutation are connected :- vtx(I;I+1;X;Y), perm(I,X), perm(I+1,Y), not edge(X,Y), not edge(Y,X). :- vtx(X;Y), bound(N), perm(N,X), perm(1,Y), not edge(X,Y), not edge(Y,X). % Compute predicate "dhc" dhc(X,Y) :- vtx(I;I+1;X;Y), perm(I,X), perm(I+1,Y). dhc(X,Y) :- vtx(X;Y), bound(N), perm(N,X), perm(1,Y). % Compute predicate "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).