Learning TSP Requires Rethinking Generalization

Abstract

End-to-end training of neural network solvers for combinatorial problems such as the Travelling Salesman Problem is intractable and inefficient beyond a few hundreds of nodes. While state-of-the-art Machine Learning approaches perform closely to classical solvers for trivially small sizes, they are unable to generalize the learnt policy to larger instances of practical scales. This talk discusses our controlled experiments into zero-shot generalization for large-scale TSP. Our study reveals that extrapolating beyond training data requires rethinking the entire neural combinatorial optimization pipeline, from network layers and learning paradigms to evaluation protocols.

Chaitanya K. Joshi

PhD Student