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 classi er, with the objective to impose only those no-overlapping constraints that have been classi ed as e ective. Preliminary experiments support the validity of the idea.
The TSP is one of the best-known problems in computer science; given a graph in which the edges have non-negative weights (usually interpreted as traveling costs), the objective is to nd a circuit visiting each node exactly once and with minimal total cost. ? Copyright ©2020 for this paper by its authors. Use permitted under Creative Commons License Attribution 4.0 International (CC BY 4.0).
This work is partially supported by GNCS-INdAM.
The TSP is notoriously NP-hard, and it has been approached through various
techniques. The most successful, to date, is Integer Linear Programming and its
variants; the current state of the art is the TSP solver Concorde [
Concorde, however, cannot address problems in which additional constraints exist, such as the TSP with time windows (in which each of the nodes can be visited only within a given time window), or the Vehicle Routing Problem (in which more than one vehicle exists).
The TSP was also addressed in the literature of Constraint Programming,
that o ers more exibility and lets one add the so-called side constraints [
One interesting case of TSP is the Euclidean TSP, in which the nodes to
be visited are associated with points in the Euclidean plane, and the distance
between each pair of points is computed through the Euclidean distance. The
Euclidean TSP is NP-Hard [20], but it admits Polynomial Time Approximation
Schemes [
In Constraint Programming, two methods exploit the information about the
problem coordinates to speed up the solution process of the TSP. Deudon et
al. [
In the other, instead, we proposed the rst approach in which the
information about the point coordinates was used to prune the search space of the
constraint programming formulation [
As all constraints, each of them must be present in memory, can be awaken
(activated) if suitable conditions occur (typically, the removal of an element
from one domain), possibly performs some pruning and then becomes dormant
again. When the solver wakes up a constraint, some computation time is spent
in awaking, scheduling the constraint and performing the checks required by
its logic. Nevertheless, the experimental results in [
However, although globally the set of constraints is worth imposing, it still might be the case that some of the n(n 1) constraints never perform any prun2 ing, and only introduce overhead. Stated otherwise, one wonders whether all these n(n 1) constraints equally contribute to the e ectiveness of the method, 2 or whether some of these constraints perform strong pruning, while others perform little or no pruning. If one were able to guess a priori which constraints will perform pruning and which, instead, will only provide overhead, she/he could avoid imposing the useless ones, reducing the overhead associated with the set of nocrossing constraints, while retaining all (or, almost all) their pruning.
In this paper, we experimentally study how much pruning is performed by each of the n(n 1) constraints. We label each constraint as useful or useless 2 considering the number of times the constraint is woken and the amount of pruning it performs. We then learn a random forest binary classi er to predict which of the constraints in a new instance will be useful and which will be useless.
Preliminary experimental results show that the approach is promising.
The rest of the paper is organized as follows: after some preliminaries, we
recap from [
Let G = (V; E; w) be a weighted graph, where V is a set of nodes, E is a set of edges, and w : E 7! R+. A path is a sequence pvs0 -vsk = vs0 es0;s1 vs1 : : : esk 1;sk vsk such that 1. vs0 ; vs1 ; : : : ; vsk 2 V and are all distinct, and 2. es0;s1 ; : : : ; esk 1;sk 2 E.
Since a path is uniquely identi ed by the sequence of its nodes (or of its edges) in the proper order, to simplify the notation we will often write paths as sequences of nodes. The length of a path p is the sum of the weights of its edges: L(p) = Pik=01 w(esi;si+1 ). Given a path pvs0 -vsk , the sequence obtained by appending esk;s0 to a path pvs0 -vsk is also called a circuit c.
The Metric TSP is a TSP in which there is an edge connecting each pair of nodes, and the distance function w enjoys the triangular inequality: w(ea;c) w(ea;b) + w(eb;c).
A Euclidean TSP is a Metric TSP in which the distance function is the Euclidean distance. Let P = fP1; : : : ; Png be a set of points, where Pi = (xi; yi). The graph associated with P is GP = (P; EP ; wP ), where EP = fei;j (Pi; Pj ) j Pi; Pj 2 P; i 6= jg and w(Pi; Pj ) = d(Pi; Pj ), where d is the Euclidean distance.
In the Constraint Programming literature, three main constraint models have
been proposed to address the TSP: the permutation representation, the successor
representation and the set variable representation [
In this paper we adopt the successor representation; it is de ned with a set of n variables Next , each ranging on the set of available nodes. Next i = j means that the successor of node i is node j. The constraint model includes pi- l
Pi
b b Pl
Q
{ an alldifferent(N ext) constraint [32], that imposes that each node is the
successor of exactly one other node,
{ a circuit(N ext) constraint [
Theorem 1. [
In order to speedup the search, in [
Clearly, this constraint should be imposed for each pair of nodes, i.e. a quadratic number of constraints.
Notice that these constraints are aimed only at improving the e ciency of the solution, they are not necessary for its correctness; they are in fact redundant constraints, and it is well known in the CP literature that redundant constraints can improve the e ciency of the search.
One question could be whether all these constraints perform e ective pruning, reducing the search space, or whether only some of them are actually useful, while others do not perform any signi cant pruning while introducing overhead. In next section, we try to reply to this question.
To evaluate the performance of each constraint we collected data while solving Euclidean TSP instances. In order to have a statistically signi cant number of instances, we decided to use randomly-generated ones. We used the generator of the DIMACS challenge [24], which provides two-dimensional instances in TSPLIB format consisting of integer-coordinate points. The generated instances can belong to two di erent classes: uniform and clustered. Points of the instances belonging to the uniform class are uniformly distributed in a 106 106 square, while points belonging to the clustered class are located in clusters that are uniformly distributed in a 106 106 square. We randomly generated instances from 15 to 30 nodes, in both classes. For each size and class we generated 32 instances, for a total of 1024 instances.
For each nocrossing constraint, in each instance, we measured 3 indicators: the number of activations Nactivations, the number of value deletions Npruned from the domain of the variables involved, and the number of failures (and therefore backtracks) generated as a result of the deletion of values. The rst two indicators were then combined to obtain a fourth one, denoted as RTIO and calculated as the ratio NaNcptirvuanteiodns . A constraint with a low RTIO wakes up many times without being able to perform pruning so it produces an unwanted overhead, while a constraint with a high RTIO can perform a much stronger pruning compared to the number of activations and therefore it is worth imposing it. Figures 2, 3 and 4 graphically show the number of value deletions, the number of failures and the RTIO respectively, for a typical instance of Euclidean TSP. In each gure, the darker the color of the line, the higher the value of the corresponding indicator. Figure 5 furthermore illustrates the nocrossing constraints that have not performed any pruning (Npruned = 0). We produced many of these gures in the hope to nd some signi cant pattern, that could help us identify the useful or the useless instances of nocrossing constraints; unluckily we were not able to observe any interesting pattern. We decided then to introduce a machine learning step.
Each constraint was labelled by means of the RTIO, which can be seen as an indicator of the \goodness" of a constraint. A constraint belonging to a certain instance I is labeled as useful if its RTIO is greater than the arithmetic mean calculated on the RTIO of all the constraints belonging to instance I, otherwise it is labeled as useless. The relation we wish to learn could be seen as a function mapping each pair of points (in a generic Euclidean TSP instance) to the set fuseful ; useless g. In principle, each point could be identi ed solely by its coordinates, but this could be a too speci c information: the e ectiveness of a constraint should be independent from rigid transformations of the whole set of points, such as rotations, axial symmetries, or even scaling.
For this reason, beside the (normalized) coordinates of each point, we computed a set of features trying to synthesize some further information that is invariant with respect to these transformations. As a guidance, we chose some features re ecting information exploited by e ective TSP solving algorithms, Fig. 2. Graphical representation of the number of value deletions performed by each nocrossing constraint in a Euclidean TSP instance. The darker the color of the segment, the higher the number of value deletions. in the hope that they could also serve as guidance for the e ectiveness of the nocrossing constraints.
One e ective algorithm for solving TSPs is the Held and Karp procedure [22], based on spanning trees. The minimum spanning tree of the set of nodes can be computed in polynomial time, and is a popular valid lower bound on the value of the optimal solution. One of the properties we chose for a pair of points is whether the segment connecting them belongs to a minimum spanning tree.
Another interesting property is the so-called necklace condition [
Finally, in [
Considering what has been introduced so far, we have identi ed the following 15 features for each nocrossing(i; Next i; j; Next j ) constraint in the dataset: { XPIN, YPIN, XPJN, YPJN: normalized coordinates of the two points Pi and Pj involved in the constraint. These coordinates are obtained, starting from the original coordinates of the points, by repositioning each instance within a square space with a 100 unit long side; { DISN: Euclidean distance calculated between points Pi and Pj using normalized coordinates; { LEVI, LEVJ: level of points Pi and Pj . The idea is to distinguish the points on the perimeter of the convex hull from the internal ones, and have a numeric value suggesting how deep in the interior of the gure is each point. The level of a point P is de ned inductively with respect to the set P of all the points:
lev(P ) = levP (P ): The level of a point P with respect to a set X is 1 if P belongs to the \exterior" of X (precisely, the perimeter HullX of the convex hull of X ) and is de ned inductively as 1 plus the level of P on the \interior" set X n HullX otherwise: levX (P ) =
1 1 + levX nHullX (P ) if P 2 HullX otherwise { CXNI, CYNI, CXNJ, CYNJ: normalized coordinates of the nearest point to Pi and Pj respectively; { NDTI, NDTJ: Euclidean distance of the closest point to Pi and Pj respectively, calculated using normalized coordinates; { NBHD: number of points contained in the circle having as diameter the segment connecting points Pi and Pj ; { NMST: (boolean value) indicates whether the segment PiPj belongs to a minimum spanning tree. 5
The dataset of labelled constraints is suitable for the application of supervised machine learning algorithms, with the goal of learning a model able to predict which of the constraints will be useful and which will be useless in a new unseen instance of the Euclidean TSP. As each constraint is labelled as useful or useless, a binary classi er can be learnt that discriminates between the negative class (useless, represented by a label equal to 0) and the positive class (useful, represented by a label equal to 1).
Among the classi cation techniques, the Random Forest (RF) approach is
known for its good computational performance and scalability. A random forest
is a meta estimator that ts a number of decision tree classi ers on various
subsamples of the dataset and uses averaging to improve the predictive accuracy and
control over tting [
2. A random subset of features (attributes) are selected for each Bi and used for the training of tree ti in the forest; 3. An information gain metric is used to grow unpruned decision trees; 4. The nal classi cation result is the most popular of the individual tree predictions.
The RF classi er can now be used to predict if on new unseen pairs of points the nocrossing constraint should be imposed, at the same time indicating to avoid imposing constraints that have been assigned the negative class (useless). The whole proposed procedure is the following: 1. A training dataset of various Euclidean TSP instances, where each constraint has been labelled according to its own RTIO, is used to learn a RF classi er; 2. Given any new instance of the problem, for whose constraints the three indicators (and so the class) are unknown, apply the classi er to nd pairs of points that are classi ed as useful for imposing the nocrossing constraint; 3. Run the instance together with the selected nocrossing constraints to solve the Euclidean TSP.
With step 3, we try to eliminate the temporal overhead that might be introduced during the search for a solution by the constraints recognized as not e ective by the random forest model.
An advantage of this procedure is that, once the classi er has been learnt, it can be reused on any new instance of the problem, without re-performing the machine learning step, which is executed only once. 6 6.1
Results of the Machine Learning step The machine learning task was carried out by training the RF classi er implemented in WEKA (version 3.8.4) [34]. The training phase was controlled by the following parameters: { -P 100: size of each bag, as a percentage of the training set size; the default value of 100 was kept; { -I 100: number of iterations (i.e., the number of trees in the random forest); { -num-slots 1: number of execution slots (thread) for constructing the ensemble. The default 1 means no parallelism; { -K 0: sets the number of randomly chosen attributes; { -M 1: the minimum number of instances per leaf; { -V 0:001: minimum numeric class variance proportion of train variance for split (it was kept the default value); { -S 1: seed for random number generator (it was kept the default value).
Given a dataset of 517,120 nocrossing constraints, collected from 1024
instances of Euclidean TSP in order to investigate the performance of the classi er,
data were split into 66% for training and the remainder for test, obtaining the
performance summary shown in Table 1 and an accuracy of 0.908. Recalling
that each pair of points can be referred to as an `example', the TP Rate is the
fraction of true positives (TP) over the total positive examples, the FP Rate is
the fraction of false positives (FP) over the total negative examples, Precision is
T P=(T P + F P ), Recall corresponds to the TP Rate, F-measure is the harmonic
mean of Precision and Recall, ROC and PR Area represent the areas under the
ROC and PR curves taking values in the range [
The classi er shows a very good performance over the test nocrossing constraints especially for the negative class (useless). After this preliminary test, the entire dataset was used for training the RF classi er, in order to feed the learning algorithm with more data, taking 544.41s to complete.
Results of the overall Euclidean TSP solver In order to evaluate the improvements in solving time obtained thanks to the predictions made by in the machine learning step, we devised a series of experiments based on randomly-generated TSPs. As for the data collection phase described in Section 4 we used the generator of the DIMACS challenge [24]. We generated a total of 1024 test instances (di erent from the ones used for learning) varying the size from 15 to 30 nodes, in both uniform and clustered classes (32 instances for each size and class).
We compared three constraint models based on the successor representation as introduced in Section 2: { the basic constraint model described in the preliminaries (denoted as ECLP), including the circuit and alldifferent constraints required by the successor representation plus the objective function; { the constraint model imposing the nocrossing constraint for all pairs of nodes (denoted as ALL); { the model imposing only the nocrossing constraints predicted as useful by the RF classi er (denoted as PRED).
3;000 2;500 ] 2;000 s [ e m iT1;500 1;000 500
ECLP ALL
PRED 700 720 740 760 780 800 820 # solved instances 840 860 880 900
All algorithms are implemented in the ECLiPSe CLP language [33]. All tests were run on ECLiPSe v. 7.0, build #54, on Intel® Xeon® E5-2630 v3 CPUs running at 2.4GHz, with one core and with 1GB of reserved memory. The time limit for each run was set to 3480s.
Figure 6 summarizes the results, in particular it shows how many of the instances can be solved by each of the three constraint models when given a time limit reported in the y-axis. The constraint model that includes only the nocrossing constraints predicted to be useful is the one obtaining the best results overall, con rming the e ectiveness of the approach proposed in this paper. The selection of constraints also increased slightly the number of instances that could be solved: among the 1024 tested instances, ECLP incurred in timeout on 158 instances, while ALL on 145, and PRED on 141. Randomly-generated TSPs instances, collected runtime data and datasets are available online2. 7
There exists a wide literature on combinations of constraint programming with
machine learning or data mining [
One of the main ideas is portfolio selection (see, e.g., the survey [26] and references therein): given a set of algorithms (or solvers) that solve a same problem,
select the best one for solving a given instance. The approach is based on obtaining data about the running time of the algorithms by collecting a high number of instances and running each of the available algorithm on each instance. Also, for each instance a number of features are computed, hopefully synthesizing the most important characteristics of the instance that make it easy or hard to solve. These can be simple statistical measures, including the size of the instance, up to measures from the literature, such as the treewidth of the instance. After that, a classi er is learned trying to predict, given the set of features of a new unseen instance, which of the available solvers will be the fastest for that speci c instance. Once a new instance is provided, the classi er is used to choose the best solver for solving it.
Our work could, in principle, be seen as an algorithm portfolio in which the classi er chooses among an exponential number of solving algorithms, each imposing a subset of the set of possible nocrossing constraints. However, we do not learn such a complex classi er (although in principle it could provide better results) because the number of possible solvers would be too large, but we try to predict which of the single nocrossing constraints will be e ective.
Although less strictly related to this paper, we cite other approaches to
combine Machine Learning and CP, including Empirical Model Learning [28, 27],
trying to learn some features of a physical system and including its input/output
relation as a new constraint, or approaches that try to learn single constraints
or a whole constraint model given examples from the user [
Various works in the CP literature address the TSP or some of its variants.
Some of them propose implementations of the circuit constraint [
Considering the objective function, various works exploit relaxations (as
usually done in Integer Linear Programming) to quickly rule out non-promising
solutions; the usual relaxations are the minimum spanning tree [
Starting with Benchimol et al. [
In this paper, we proposed to predict and select the set of nocrossing constraints in Euclidean TSPs formulated in CP.
The rst experimental results are encouraging, but more extensive experiments will also be carried out. The performance of the solver with constraints pruned by the RF classi er will be compared with the same number of constraints but pruned at random, to validate the relevance of the proposed approach. We also believe that much more e ciency could be obtained in future research.
One rst direction is re ning the RF model to check if better performance may be obtained, but also testing other supervised learning techniques. For instance it would be interesting to predict, instead of two classes, the actual ratio of pruning power versus activations NaNcptirvuanteiodns , run experiments imposing only those nocrossing constraints whose ratio is predicted to be higher than a given threshold, and experimentally nd the best possible value of the threshold. This changes the machine learning step from a classi cation to a regression task, which, on the other hand, may be more challenging. One could then move from supervised learning to reinforcement learning techniques and thus avoid collecting a training set.
Some improvement could be obtained by expanding the dataset of
experiments, i.e. by running experiments in more instances to widen the available data
about number of activations and pruning of the nocrossing constraints. Also,
in the current dataset only one search heuristic was employed, namely max
regret [
Another method could be to use data augmentation techniques; for example by rotating all points in an instance of a same angle, one obtains the same TSP instance (and the optimal solution does not change), so in principle the number of activations should not change, while the input data would be di erent from the viewpoint of the machine learning algorithm, since the point coordinates would change.
An enlargement of the set of features, collected during the creation of the dataset, is already planned, so that the learned classi er relies less on the point coordinates and more on the synthesized features (e.g. number of edges crossed by the segment PiPj related to the constraint nocrossing(i; Next i; j; Next j )).
Finally, instead of learning a classi er that chooses the set of nocrossing constraints that should be imposed a priori, one could use more dynamic strategies, like removing during search the nocrossing constraints that result less e ective because they have not obtained signi cant pruning in the last activations. One source of inspiration could be the strategies used in SAT solvers to forget some of the nogoods [21]. 20. Garey, M.R., Graham, R.L., Johnson, D.S.: Some NP-complete geometric problems. In: Proceedings of the Eighth Annual ACM Symposium on Theory of Computing. pp. 10{22. STOC '76, ACM, New York, NY, USA (1976) 21. Gent, I.P., Miguel, I., Moore, N.C.A.: An empirical study of learning and forgetting constraints. AI Commun. 25(2), 191{208 (2012). https://doi.org/10.3233/AIC2012-0524 22. Held, M., Karp, R.M.: The traveling-salesman problem and minimum spanning trees. Operations Research 18, 1138{1162 (1970) 23. Isoart, N., Regin, J.C.: Integration of structural constraints into tsp models. In: International Conference on Principles and Practice of Constraint Programming. pp. 284{299. Springer (2019) 24. Johnson, D.S., McGeoch, L.A.: Experimental analysis of heuristics for the stsp. In:
The traveling salesman problem and its variations, pp. 369{443. Springer (2007) 25. Kaya, L.G., Hooker, J.N.: A lter for the circuit constraint. In: Benhamou, F. (ed.) Principles and Practice of Constraint Programming - CP 2006, 12th International Conference, CP 2006, Nantes, France, September 25-29, 2006, Proceedings. Lecture Notes in Computer Science, vol. 4204, pp. 706{710. Springer (2006) 26. Kottho , L.: Algorithm selection for combinatorial search problems: A survey. In:
Bessiere et al. [
Intell. 244, 343{367 (2017). https://doi.org/10.1016/j.artint.2016.01.005 29. Mitchell, J.S.B.: Guillotine subdivisions approximate polygonal subdivisions: A simple polynomial-time approximation scheme for geometric TSP, k-MST, and related problems. SIAM J. Comput. 28(4), 1298{1309 (1999) 30. Pesant, G., Gendreau, M., Potvin, J., Rousseau, J.: An exact constraint logic programming algorithm for the traveling salesman problem with time windows. Transportation Science 32(1), 12{29 (1998) 31. Provost, F.J., Fawcett, T.: Robust classi cation for imprecise environments. Machine Learning 42(3), 203{231 (2001) 32. Regin, J.: A ltering algorithm for constraints of di erence in CSPs. In: HayesRoth, B., Korf, R.E. (eds.) Proceedings of the 12th National Conference on Arti cial Intelligence, Seattle, WA, USA, July 31 - August 4, 1994, Volume 1. pp. 362{367. AAAI Press / The MIT Press (1994) 33. Schimpf, J., Shen, K.: Eclipse - from LP to CLP. TPLP 12(1-2), 127{156 (2012) 34. Witten, I.H., Frank, E., Hall, M.A.: Data Mining: Practical Machine Learning Tools and Techniques. Morgan Kaufmann Series in Data Management Systems, Morgan Kaufmann, 3 edn. (2011)