Track papers across labs, topics, and trends.
Search papers, labs, and topics across Lattice.
This paper introduces NICO-TSP, a novel neural improvement framework for the Traveling Salesperson Problem (TSP) that learns the search procedure itself. NICO-TSP uses edge tokens aligned with the 2-opt neighborhood operator, scores moves directly without positional encodings, and employs a two-stage training process of imitation learning followed by critic-free reinforcement learning. Results show NICO-TSP achieves superior step-efficiency, generalization to larger instances, and performance compared to learned and heuristic search baselines, making it a competitive alternative to classical local search.
Neural nets can beat classical heuristics at the Traveling Salesperson Problem, but only if you rethink the architecture from the ground up to match the mechanics of local search.
Most neural solvers for the Traveling Salesperson Problem (TSP) are trained to output a single solution, even though practitioners rarely stop there: at test time, they routinely spend extra compute on sampling or post-hoc search. This raises a natural question: can the search procedure itself be learned? Neural improvement methods take this perspective by learning a policy that applies local modifications to a candidate solution, accumulating gains over an improvement trajectory. Yet learned improvement for TSP remains comparatively immature, with existing methods still falling short of robust, scalable performance. We argue that a key reason is design mismatch: many approaches reuse state representations, architectural choices, and training recipes inherited from single-solution methods, rather than being built around the mechanics of local search. This mismatch motivates NICO-TSP (Neural Improvement for Combinatorial Optimization): a 2-opt improvement framework for TSP. NICO-TSP represents the current tour with exactly $n$ edge tokens aligned with the neighborhood operator, scores 2-opt moves directly without tour positional encodings, and trains via a two-stage procedure: imitation learning to short-horizon optimal trajectories, followed by critic-free group-based reinforcement learning over longer rollouts. Under compute-matched evaluations that measure improvement as a function of both search steps and wall-clock time, NICO-TSP delivers consistently stronger and markedly more step-efficient improvement than prior learned and heuristic search baselines, generalizes far more reliably to larger out-of-distribution instances, and serves both as a competitive replacement for classical local search and as a powerful test-time refinement module for constructive solvers.