» ASP Competition | |
|
Travelling SalespersonProblem descriptionThe 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 formatAn input consists of the following parts: a.
The vertices of the input graph are numbered and given by instances of "vtx" as follows: b.
There is exactly one instance of predicate "bound" for the vertex with greatest number n: c.
The edges of the graph are given by instances of "edge" as follows: d.
For each edge(i_1,i_2),
there is exactly one instance of "edgewt"
providing the edge's (positive) weight w_i: e.
Finally, there is exactly one instance of "maxweight"
specifying the maximum weight w for admissible Hamiltonian cycles: For further illustration, compare the instances available at asparagus. Output formatA 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 |