Purity Law for Generalizable Neural TSP Solvers
This addresses the problem of poor generalization in neural TSP solvers for researchers and practitioners, offering a novel training paradigm that is incremental but impactful.
The paper tackles the challenge of generalization in neural Traveling Salesman Problem (TSP) solvers by uncovering the Purity Law (PuLa), a structural principle showing edge prevalence grows exponentially with vertex sparsity in optimal solutions, and proposes Purity Policy Optimization (PUPO) to align neural solutions with this law, significantly enhancing generalization performance without extra inference cost.
Achieving generalization in neural approaches across different scales and distributions remains a significant challenge for the Traveling Salesman Problem~(TSP). A key obstacle is that neural networks often fail to learn robust principles for identifying universal patterns and deriving optimal solutions from diverse instances. In this paper, we first uncover Purity Law (PuLa), a fundamental structural principle for optimal TSP solutions, defining that edge prevalence grows exponentially with the sparsity of surrounding vertices. Statistically validated across diverse instances, PuLa reveals a consistent bias toward local sparsity in global optima. Building on this insight, we propose Purity Policy Optimization~(PUPO), a novel training paradigm that explicitly aligns characteristics of neural solutions with PuLa during the solution construction process to enhance generalization. Extensive experiments demonstrate that PUPO can be seamlessly integrated with popular neural solvers, significantly enhancing their generalization performance without incurring additional computational overhead during inference.