A First Guess is Rarely the Final Answer: Learning to Search in the Traveling Salesperson Problem

Andoni Irazusta Garmendia · 2026

Read A First Guess is Rarely the Final Answer: Learning to Search in the Traveling Salesperson Problem by Andoni Irazusta Garmendia (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2604-06940.txt.

Introduction

Irazusta presents NICO-TSP, a search method for the Traveling Salesperson Problem. Most neural solvers output one solution, yet users spend extra compute on sampling or search, so the paper asks whether search can be learned. NICO-TSP learns a policy of 2-opt moves, representing the tour with matched edge tokens and scoring moves without positional encodings. Training mixes imitation of short optimal runs with group reinforcement learning over rollouts. Under compute-matched tests it improves faster per step than prior baselines and generalizes better to larger unseen instances.

Catalog record

CREATORAndoni Irazusta Garmendia
YEAR2026
COLLECTIONPAPERS
FORMATTXT
FILE SIZE55406
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2604.06940

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

A First Guess is Rarely the Final Answer: Learning to Search in the Traveling Salesperson Problem Andoni Irazusta Garmendia Abstract 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 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. 1 Introduction A prevailing paradigm in Neural Combinatorial Optimization (NCO) 2 ; 14 is to learn constructive policies that generate a solution from scratch 8 ; 9 ; 11 . This emphasis has led to objectives and evaluation protocols that prioritize the speed and quality of the first solution. However, in many realistic settings, the value of a learned solver is determined less by its initial output than by the solution quality it can achieve under a fixed compute budget. As a result, one-shot policies are often integrated into iterative inference pipelines that spend additional budget on search and refinement, for example, via sampling 9 , beam search 19 , local search 4 , or active search 6 . This common practice highlights a structural mismatch between how these models are optimized (single-solution output) and how they are ultimately deployed (budgeted iterative improvement). In this work, we treat search as the central learned object rather than a post-hoc patch. We focus on the Traveling Salesperson Problem (TSP) 1 , a canonical testbed for NCO, and study neural improvement : policies that iteratively apply local modifications to improve a candidate solution 20 ; 3 ; 7 . Neural improvement for TSP has remained comparatively underexplored and often underperforms constructive policies, not because local improvement is inherently weaker, but because existing learning-based formulations are misaligned with the improvement regime. First, most methods reuse node-centric representations designed for construction, while executing edge-based operators such as 2-opt; this forces the policy to reason about actions through an indirect state parameterization. Second, many architectures encode the current tour via tour positional encodings over nodes, introducing a fragile coordinate system whose semantics change with n and that can degrade sharply under scale shift. Third, training is typically posed as long-horizon reinforcement learning in a vast combinatorial space, where improvements become sparse near local optima and credit assignment across sequences of actions is unstable, leading to high-variance learning signals and slow optimization. We address these bottlenecks with four main contributions in a framework we term Neural Improvement for Combinatorial Optimization applied to the TSP (NICO-TSP): • Edge-centric representation. We introduce an edge-token representation that uses the n tour edges as the primary tokens and augments them with local geometric context. In contrast to pairwise edge representations that scale as O(n^{2}) tokens 15 , our representation is O(n) and aligns the model inputs with the objects directly edited by 2-opt. • Edge-attention policy without positional encodings. We propose an encoder–decoder architecture that contextualizes edge tokens and scores 2-opt actions directly from pairs of edge representations. The model does not rely on tour positional encodings, avoiding a source of poor large-scale generalization. • Two-stage learning. We develop a two-stage training procedure that combines: (i) imitation learning with exact K -step lookahead and set-valued supervision, and (ii) critic-free group-based reinforcement learning, which further improves the policy through intra-instance competition. • Strong empirical performance. We show that NICO-TSP outperforms post-hoc search procedures applied to neural constructive methods, while also remaining competitive as a standalone neural improvement policy. 2 Background 2.1 Traveling Salesperson Problem The Traveling Salesperson Problem (TSP) 1 asks for the minimum-length Hamiltonian cycle through n cities. Formally, for an instance x with city set V=\{1,\dots,n\} and distances d_{ij}\geq 0 , a tour is a permutation \pi=(\pi_{1},\dots,\pi_{n})\in\Pi_{n} with cost C(\pi\mid x)=\sum_{k=1}^{n}d_{\pi_{k},\pi_{k+1}},\qquad\pi_{n+1}\equiv\pi_{1}, (1) and the goal is to find \pi^{\star}=\arg\min_{\pi\in\Pi_{n}}C(\pi\mid x) . 2.2 Neural Improvement as a Markov Decision Process We frame Neural Improvement for the Traveling Salesperson Problem as a Markov Decision Process (MDP) in which a stochastic policy p_{\theta} iteratively refines a candidate tour through local modifications. The goal is to learn a general improvement strategy: from a set of training instances, we optimize parameters \theta so that the resulting policy transfers to unseen TSP instances. We adopt an episodic formulation with a fixed improvement budget of T steps, i.e., t\in\{0,\dots,T-1\} 1 1 1 The step budget T can differ between training and inference (e.g., short episodes for efficient learning and longer rollouts at test time). . A state s_{t}\in\mathcal{S} consists of the TSP instance x (fixed within an episode), the current candidate tour \pi_{t} , and an auxiliary context variable c_{t} that summarizes any historical information required to preserve the Markov property, i.e., s_{t}=(x,\pi_{t},c_{t}) . All other quantities used by the policy are deterministic features derived from x and \pi_{t} . Given s_{t} , the policy p_{\theta}(a\mid s_{t}) defines a distribution over actions a_{t}\in\mathcal{A}(s_{t}) , where \mathcal{A}(s_{t}) is the set of feasible local moves under a chosen neighborhood operator. In this paper, we use the 2-opt neighborhood: an action a_{t}=(i,j) selects two non-adjacent tour edges. We take 1\leq i<j\leq n with j\geq i+2 and (i,j)\neq(1,n) , which replaces edges (\pi_{t}[i],\pi_{t}[i+1]) and (\pi_{t}[j],\pi_{t}[j+1]) by (\pi_{t}[i],\pi_{t}[j]) and (\pi_{t}[i+1],\pi_{t}[j+1]) . The transition is deterministic: s_{t+1}=(x,\pi_{t+1},c_{t+1}) . 3 Methods This section introduces the representation, policy architecture, and learning framework of NICO-TSP. Full implementation details are provided in Appendix A . 3.1 Problem Representation Most neural improvement policies for TSP use node tokens and inject the current tour through solution-dependent features, often tour positional encodings 20 ; 13 . This is indirect for 2-opt, whose actions are naturally defined over pairs of tour edges, and such positional encodings can generalize poorly across problem sizes, since both the numerical range and the semantic role of positions vary with tour length. We therefore represent the current solution directly as a sequence of tour edges and use these edges as the central tokens throughout the policy network. Concretely, given the current tour \pi_{t}=(\pi_{t}[1],\ldots,\pi_{t}[n]) , we form the length- n cyclic sequence of directed edges u_{k}=\pi_{t}[k],\qquad v_{k}=\pi_{t}[k+1],\qquad e_{k}=(u_{k}\rightarrow v_{k}),\qquad k=1,\ldots,n, (2) with

Read the complete text