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 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 speed-up the solution of Euclidean instances in CP, by imposing a quadratic number of so-called no-overlapping constraints. In this work, we observe that not all the no-overlapping constraints are equally useful: by experimental analysis, some of them provide a speed-up, while others only introduce overhead. Thus, it is important to define a way to classify useful constraints. To do so, we use machine learning approaches with the objective to impose only those no-overlapping constraints that have been classified as effective. We compare two classifiers based on Random Forest and Neural Networks, which show to be effective, with a slight prevalence for Random Forest.