TSP with Predictions: Heatmap to Tour with Provable Guarantees

The Traveling Salesperson Problem (TSP) has long served as a benchmark for evaluating the strength of optimization techniques in the classical theory of algorithms. In recent efforts to apply ML to algorithmic problems, TSP has also become a natural testbed for the development of ML-based techniques. A common approach is to train a neural network to output a heatmap estimating the likelihood of each edge to be part of the optimal tour; however, converting such a heatmap into an actual tour remains a non-trivial and often computationally intensive step. In this work, we propose algorithms for transforming heatmaps into tours with theoretical guarantees linking the achieved approximation ratio to the quality of the provided heatmap. In the spirit of *algorithms with predictions*, our results can be described as $(1+2\eta/OPT)$-approximation algorithms, where $\eta$ denotes the L1 distance between the prediction (heatmap) and an optimal solution (tour). Since the previous works lack such explicit guarantees, we compare our approach against them experimentally.

The Travelling Salesperson Problem (TSP) is to find the shortest round trip through a set of points in a map. It is a classic hard optimization problem, and it has many real-world uses, e.g., in delivery routing, but also in electronic circuit design. Recent machine learning methods often try to help by predicting which roads are likely to appear in the best route. However, such predictions still need to be turned into a valid round trip, and this final step is difficult: simple methods can waste good predictions, while more powerful search methods can be slow and may reduce the role of the machine learning model. We design algorithms that turn such per-road predictions into complete tours. Our methods come with theoretical worst-case guarantees: when the predictions are close to a good route, the length of the tour we produce is also close to optimal. We build on a classic Christofides algorithm for TSP, but we change it so that it can make reliable use of uncertain predictions. This gives machine learning models a more efficient and safer way to help solve TSP. In experiments, our approach uses predicted road probabilities more effectively than simple methods, suggesting that better prediction models can directly lead to better routes.