LocalEscaper: A Weakly-supervised Framework with Regional Reconstruction for Scalable Neural TSP Solvers
This addresses scalability and data efficiency issues for researchers and practitioners in combinatorial optimization, though it appears incremental as it builds on existing neural solver methods.
The paper tackled the challenges of neural solvers for the Traveling Salesman Problem (TSP) by proposing LocalEscaper, a weakly-supervised framework that combines supervised and reinforcement learning advantages to train on low-quality labels, and it outperformed existing neural solvers in experiments.
Neural solvers have shown significant potential in solving the Traveling Salesman Problem (TSP), yet current approaches face significant challenges. Supervised learning (SL)-based solvers require large amounts of high-quality labeled data, while reinforcement learning (RL)-based solvers, though less dependent on such data, often suffer from inefficiencies. To address these limitations, we propose LocalEscaper, a novel weakly-supervised learning framework for large-scale TSP. LocalEscaper effectively combines the advantages of both SL and RL, enabling effective training on datasets with low-quality labels. To further enhance solution quality, we introduce a regional reconstruction strategy, which is the key technique of this paper and mitigates the local-optima problem common in existing local reconstruction methods. Experimental results on both synthetic and real-world datasets demonstrate that LocalEscaper outperforms existing neural solvers, achieving remarkable results.