TSP and the associated class of routing problems have also emerged as a challenging testbed for learning-driven approaches to combinatorial optimization.
Whereas generalization to problem instances larger and more complex than those seen in training has at least partially been demonstrated on non-sequential problems such as SAT, MaxCut, Minimum Vertex Cover [1]}, [2]}, [3]}It is worth noting that classical algorithmic and symbolic components such as graph reduction, sophisticated tree search as well as post-hoc local search have been pivotal and complementary to neural networks in enabling such generalization [2]}, [5]}.,
the same architectures do not show strong generalization for TSP.
For example, the furthest insertion heuristic outperforms or is competitive with state-of-the-art approaches for TSP above tens of nodes, see Figure D.1.(e) and (f) from Khalil et al. [1]} or Figure 5 from Kool et al. [7]}, despite using more computation and data than our controlled experimental study.
