This paper presents an initial technical investigation of these questions on the classical Travelling Salesman Problem, with the broader goal of developing robust and reliable learning-driven solvers for any combinatorial problem.
TSP has a rich history of serving as an engine of discovery for general purpose techniques in applied mathematics, including foundational work in Mixed Integer Programming [1]}, Branch-and-bound methods [2]}, heuristic search [3]} and early neural networks [4]}, [5]}.
This line of work has already inspired novel reinforcement learning algorithms [6]} and powerful Graph Neural Network architectures [7]}, [8]}.
Beyond combinatorial problems, designing statistical models that can generalize out-of-training-distribution is seen as an important challenge for the entire Machine Learning community [9]}, [10]}, [11]}, [12]}, [13]}, [14]}, [15]}.
In the near future, we hope TSP and combinatorial problems can serve as a challenging and practical benchmark for studying generalization in deep learning.
