New Encodings of the Euclidean Traveling Salesperson Problem in Constraint Answer Set Programming on Difference Logic

The Travelling Salesperson Problem (TSP) is a very well-known problem in computer science. Many real-world instances belong to the class of Euclidean TSP, in which the nodes to be visited lie on the Euclidean plane, and additional information is available with respect to the generic TSP, i.e. the coordinates of the nodes to be visited are known. In previous publications, we showed that the additional available information can be exploited to speed up the search, both in Constraint Logic Programming (CLP) and in Answer Set Programming (ASP). Constraint ASP (CASP) is a framework that joins CLP and ASP, and it aims at combining the features of both languages. In this article, we address the (Euclidean) TSP in CASP, and more specifically in the clingo[DL] language and solver. We propose new encodings for the TSP in clingo[DL]; the new encodings are applicable to the general TSP (also to instances that are not Euclidean) and show a speedup of several orders of magnitude with respect to previous encodings. A further speedup can be obtained in Euclidean instances by exploiting geometric reasoning.