# A New Constructive Heuristic Driven by Machine Learning for the Traveling Salesman Problem
## 2 Materials and Methods
### The ML-Constructive Algorithm  
The _ML-Constructive_ starts as a modified version of MF, then concludes the tour exploiting the CW heuristic. The ML model behaves consequently as a glue since it is crucial to determine the partial solution available at the switch between solvers. The list of promising edges \(L_{P}\) and the confidence level of the ML decision-taker are critical specifications to set in the heuristic before than it runs. The reasons behind our promising list building choices were widely discussed in Section 2.3. While the confidence level is used to handle the exploitation vs exploration trade-off. It consists of a simple threshold applied to the predictions made by the ML system. If the predicted probability that validates the insertion is greater than such threshold, then the insertion is applied. The value of 0.99 has been verified to provide good results on tested instances. Since, lower values increase the occurrence of false-positive cases, thus leading to the inclusion of edges that are not optimal. On the other hand, higher values of it decrease the occurrence of true-positive cases, hence increasing the challenge of the second phase. The overall pseudo-code for the heuristic is shown in Algorithm 1. Firstly, the CLs for each vertex in the instance are computed (line 2). We noticed that considering just the closest thirty vertices for each CL was a good option. As mentioned, just the first two connections are considered in \(L_{P}\), while the other vertices are used to create the local context in the image. The CL construction takes a linear number of operations for each vertex, and the overall time complexity for constructing it is \(O(n^{2})\). Since finding the nearest vertex of a given vertex it takes linear time, the search for the second nearest takes the same time (after removing the previous from the neighborhood). So on until the thirtieth nearest vertex is found. As only the first thirty edges are searched, the operation can be completed in linear time. Then, promising edges are inserted in \(L_{P}\) (line 3), then repeating edges are deleted to avoid unnecessary operations (line 4). The list is sorted according to the position in the CL and the cost values (line 5). All the edges that are the first nearest will be found first and sorted according to \(c_{ij}\), then the second nearest and so on. Since only the first two edges for each CL can be in the list, the sorting task is completed in \(O(n\log n)\). Several orders for \(L_{P}\) were preliminary tested--e.g., employing descending cost values or even savings to sort the edges in \(L_{P}\)--but experiments suggested that sorting the list according to ascending cost values is the best arrangement. The first phase of _ML-Constructive_ takes part. An empty solution \(X=0\) is initialized (line 6), and following the order in \(L_{P}\) a variable \(l\) is updated with the edge considered for the addition (line 7). At first, \(l\) is checked to ensure that the edge complies the TSP constraints (Equations (2)-(4)). Then the ML decision-taker is queried to confirm the addition of the edge \(l\). If the predicted probability is higher than the confidence level, the edge is added to the partial solution (lines 11 and 14). To evaluate the number of operations that this phase consumes, we must split the task according to the various sub-routines which are acted at each new addition in the solution. The \"if\" statements (lines 9, 13, 23 and 26) check that the constraints (2) and (3) are complied. They verify that both extremes of the attaching edge \(l\) exhibit at most one connection in the current solution. The operation is computed with the help of hash maps, and it takes constant time for each considered edge \(l\). The tracker verification (lines 10 and 24) ensures that \(l\) will not create an inner-loop (Equation (4)). This sub-routine is applied only after it is checked that both extremes of \(l\) have exactly one connection, each in the current partial solution.