Encoding Class TravelingSalespersonSuite

Class Tree
Description Given an integer w and an undirected graph G=(V,E), where every edge (u,v) is associated with a positive weight w_{u,v}, the goal is to find a Hamiltonian cycle in G (a simple cycle that visits all vertices in G exactly once) such that the sum of the edges in the cycle is at most w.

Input Format
============
Each input graph is stored in a plain text file. The format of the file is as follows:

a. The first line defines the number of vertices in the graph, using the predicate "bound(n)." For instance:
bound(17).
specifies that the graph has 17 vertices.

b. Given that "bound(n)." is the first line, the next n lines define vertices by means of a predicate "vtx" .

vtx(1).
vtx(2).
...
vtx(n).

c. The definition of edges follows that of the vertices. The predicate used to define edges is a binary predicate "edge" with edge(i,j) meaning that i and j are connected with an edge:

edge(1,3).
edge(4,2).
...

Loops are disallowed (no line of the form "edge(i,i)."). In addition, if there is a line "edge(i,j).", there will not be the line
"edge(j,i).".

d. The next line contains a single predicate "maxweight(w).", which specifies the weight bound of the Hamiltonian cycle. For example,

maxweight(1200).

d. The next set of lines contain the definition of edge weights:

weight edgewt(1,2) = 8.
weight edgewt(2,1) = 8.
...

For each undirected edge (u,v), we include two identical weights for both the pair (u,v) and the pair (v,u).

Example
bound(4).
vtx(1).
vtx(2).
vtx(3).
vtx(4).
edge(1,2).
edge(3,2).
edge(4,3).
edge(1,4).
maxweight(10).
weight edgewt(1,2) = 2.
weight edgewt(2,1) = 2.
weight edgewt(2,3) = 3.
weight edgewt(3,2) = 3.
weight edgewt(3,4) = 1.
weight edgewt(4,3) = 1.
weight edgewt(1,4) = 3.
weight edgewt(4,1) = 3.

Output Requirement
==================
The solution must be represented by means of a binary predicate "hc". That is atoms of the form "hc(i,j)" must describe all edges of the hamiltonian cycle. An atom hc(i,j) belongs to the answer-set if and only if 1) edge(i,j) belongs to the Hamiltonian cycle; and 2) edge(i,j) is defined in the input instance. For example, if edge(2,3) is defined in
the input instance and it belongs to the Hamiltonian cycle, then hc(2,3) belongs to the answer-set (instead of hc(3,2)).

For our example input, the following set of ground atoms specifies a valid solution:
hc(1,2)
hc(3,2)
hc(4,3)
hc(1,4)

Authors: Lengning Liu and Miroslaw Truszczynski
Affiliation: University of Kentucky
Email: {lliu1, mirek}@cs.uky.edu
Encodings
1 - 5 of 5