rcra-2020

This repository contains datasets related to the paper: Improving the efficiency of Euclidean TSP solving in Constraint Programming by predicting effective nocrossing constraints (Elena Bellodi, Alessandro Bertagnon, Marco Gavanelli, Riccardo Zese) submitted at the 27th RCRA International Workshop on Experimental Evaluation of Algorithms for Solving Problems with Combinatorial Explosion.

• The ml-instances directory contains 1024 Euclidean TSP instances, generated in 2 classes (uniform and clustered) using the generator of the DIMACS challenge (8th DIMACS Implementation Challenge: The Traveling Salesman Problem). Each instance is provided in TSPLIB format (.tsp) and in a Prolog-like syntax (.pl). All these instances have been solved and the collected runtime data have been used to build the ml-dataset used to train the Random Forest (RF) classifier.

• The etsp-solver-instances directory contains 1024 Euclidean TSP instances (different from the ones above), generated in 2 classes (uniform and clustered) using the generator of the DIMACS challenge (8th DIMACS Implementation Challenge: The Traveling Salesman Problem). Each instance is provided in TSPLIB format (.tsp) and in a Prolog-like syntax (.pl). Each .arff (Attribute Relationship File Format) file contains the features of each constraint ready to be used for classification with Weka workbench for machine learning (Weka). Each .pl file also contains Prolog facts in the form: nocross(A,B) that indicate the pairs of nodes on which the nocrossing constraint should be imposed according to the Random Forest (RF) classifier prediction.