Graph Representation for Learning the Traveling Salesman Problem

Training deep learning models for solving the Travelling Salesman Problem (TSP) directly on large instances is computationally challenging. An approach to tackle large-scale TSPs is through identifying elements in the model or training procedure that promotes out-of-distribution (OoD) generalization, i.e., generalization to samples larger than those seen in training. The state-of-the-art TSP solvers based on Graph Neural Networks (GNNs) follow different strategies to represent the TSP instances as input graphs. In this paper, we conduct experiments comparing different graph representations finding features that lead to a better OoD generalization.