Travel the Same Path: A Novel TSP Solving Strategy
This provides a faster exact solver for TSP, a foundational combinatorial optimization problem in theoretical computer science, though it appears incremental as it builds on existing imitation learning and graph neural network methods.
The paper tackles the Traveling Salesman Problem (TSP) by using imitation learning to speed up a deterministic algorithm while maintaining exact solutions, demonstrating that a graph neural network trained on small instances can solve large instances faster than baselines.
In this paper, we provide a novel strategy for solving Traveling Salesman Problem, which is a famous combinatorial optimization problem studied intensely in the TCS community. In particular, we consider the imitation learning framework, which helps a deterministic algorithm making good choices whenever it needs to, resulting in a speed up while maintaining the exactness of the solution without suffering from the unpredictability and a potential large deviation. Furthermore, we demonstrate a strong generalization ability of a graph neural network trained under the imitation learning framework. Specifically, the model is capable of solving a large instance of TSP faster than the baseline while has only seen small TSP instances when training.