Improving the efficiency of euclidean TSP solving in constraint programming by predicting effective nocrossing constraints

The Traveling Salesperson Problem (TSP) is a well-known problem addressed in the literature through various techniques, including Integer Linear Programming, Constraint Programming (CP) and Local Search. Many real life instances belong to the subclass of Euclidean TSPs, in which the nodes to be visited are associated with points in the Euclidean plane, and the distance between them is the Euclidean distance. A well-known property of the Euclidean TSP is that no crossings can exist in an optimal solution. In a previous publication, we exploited this property to speedup the solution of Euclidean instances in CP, by imposing a number of so-called no-overlapping constraints. The number of imposed constraints is quadratic in the number of nodes of the TSP. In this work, we observe that not all the no-overlapping constraints are equally useful: by experimental analysis, some of them provide a speedup, while others only introduce overhead. We use a supervised machine learning approach on them to learn a binary classifier, with the objective to impose only those no-overlapping constraints that have been classified as effective. Preliminary experiments support the validity of the idea.