# A New Constructive Heuristic Driven by Machine Learning for the Traveling Salesman Problem
## 2 Materials and Methods
### The General Idea  
In light of the statistical study presented in Section 2.2, we propose a constructive heuristic called _ML-Constructive_. The heuristic follows the edge addition process (see MF and CW in Section 2.1) extended by an auxiliary operation that asks the ML to agree for any attaching edge during a first phase. The goal is to avoid as much as possible adding bad edges in the solution while allowing the addition of promising edges which are considered auspicious by the ML model. We emphasize that our focus is not on the development of highly efficient ML architectures, but rather on the successful interaction between ML and optimization techniques. Therefore, the ML is conceived to act as a decision-taker and the optimization heuristics as the texture of the solution building story. The result is a new hybrid constructive heuristic that succeeds in scaling up to big problems while keeping the improvements achieved thanks to ML. As aforementioned, the ML is exploited just in situations where the data do not suggest underrepresented cases, and since about 95% of the optimal edges are connections with one of the closest five vertices of a CL, only such subset of edges is initially considered to test the ML performances. Recall that it is a common practice to avoid employing ML in the prediction of rare events. Instead, it is commonly suggested to apply ML preferably in cases where a certain level of pattern recognition can be confidently detected. For this reason, our solution is designed to construct TSP tours in two phases. The first employs ML to construct partial solutions (Figure 4). While the second uses the CW heuristic to connect the remaining free vertices and complete the TSP tour. Initially, during the first phase, considered most likely edges to be found in the optimal tour are collected in the list of promising edges \(L_{P}\). To appropriately choose these edges, several experiments were carried out and results are shown in Table 2. The strategy used to build the promising list was to include the edges of the first \(m\) vertices of each CL, considering the \(m\) value ranging from 1 to 5. The ML was in charge of predicting whether the edges under consideration in \(L_{P}\) were in the optimal solution or not. Experiments were  
Figure 4: First phase partial solution constructed with the ML predictions. Vertices in light blue are free for the second phase of _ML-Constructive_. The instance is the KroA100 from the TSPLIB collection. handled adopting the same ResNet [20] architecture and procedure explained in Section 2.5, but the ML was trained on different data to be consistent with the \(m\) tested value. Several classic metrics were compared for the different \(m\): the True Positive Rate (TPR), the False Positive Rate (FPR), and their difference [50]. Please note that ML objectives are to keep the FPR small, meanwhile to obtain good results in terms of TPR. Keeping a small FPR ensures that during the second phase the _ML-Constructive_ has an higher probability in detecting good edges, meanwhile with a high TPR the search space for the second phase is hopefully reduced (Appendix B). In terms of TPR, it seems to be the best choice to include just the shortest edge in \(L_{P}\) (\(m=1\)), but by checking the FPR in Table 2 it becomes obvious that the ML has learned to predict almost always an agreement for \(m=1\). Therefore, such a behavior is undesirable and it leads to a high FPR, and hence to worse solutions during the second phase. However, if the difference between TPR and FPR is taken into account, the best arrangement is when the first two shortest edges are put into the list (\(m=2\)). Although other arrangements might show to be effective as well, the selection through positions in the CLs and the selection of the first two shortest edges in each CL are proven to be efficient by the results. Recall that too many edges in \(L_{P}\) can be confusing since outliers and classes with severe distribution skew can appear.