Travelling Salesperson

Problem description

The Travelling Salesperson Problem (TSP for short) is about finding a Hamiltonian cycle (a cycle that visits each vertex exactly once) in an undirected graph G = (V,E), where V is the set of vertices and E the set of edges. Every edge {i,j} in E is associated with a positive weight w_{i,j}, and the sum of edges belonging to an admissible Hamiltonian cycle must not exceed a maximum weight w.

Input format

An input consists of the following parts:

a. The vertices of the input graph are numbered and given by instances of "vtx" as follows:

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

b. There is exactly one instance of predicate "bound" for the vertex with greatest number n:

bound(n).

c. The edges of the graph are given by instances of "edge" as follows:

edge(1_1,1_2). edge(2_1,2_2). ... edge(m_1,m_2).

An instance edge(i_1,i_2) specifies that there is an undirected edge between vertex i_1 and vertex i_2. As the graph is undirected, edge(i_1,i_2) is equivalent to edge(i_2,i_1), and only one of them needs to belong to the input.

d. For each edge(i_1,i_2), there is exactly one instance of "edgewt" providing the edge's (positive) weight w_i:

edgewt(i_1,i_2,w_i).

e. Finally, there is exactly one instance of "maxweight" specifying the maximum weight w for admissible Hamiltonian cycles:

maxweight(w).

For further illustration, compare the instances available at asparagus.

Output format

A solution is represented by means of a binary predicate "cycle" such that, for each instance cycle(i_1,i_2), we have that at least one of edge(i_1,i_2) and edge(i_2,i_1) belongs to the input. The edges corresponding to the instances of "cycle" must form a Hamiltonian cycle in the undirected input graph, and the sum of their weights must not exceed maximum weight w given in the input. Finally, the instances of "cycle" are directed, and the Hamiltonian cycle must be obtained by visiting i_2 after i_1 for each instance cycle(i_1,i_2) in a solution.

Author: Lengning Liu, Miroslaw Truszczynski, and Martin Gebser
Affiliation: University of Kentucky and University of Potsdam