![[2602.20175] Tensor Network Generator-Enhanced Optimization for Traveling Salesman Problem](https://arxiv.org/static/browse/0.3.4/images/arxiv-logo-fb.png){kind=logo}
[2602.20175] Tensor Network Generator-Enhanced Optimization for Traveling Salesman Problem
Summary
This article presents a novel optimization framework using tensor networks to tackle the Traveling Salesman Problem (TSP), demonstrating superior performance over classical heuristics.
Why It Matters
The Traveling Salesman Problem is a fundamental challenge in combinatorial optimization with wide applications in logistics and routing. This research introduces an innovative approach that leverages tensor networks, potentially improving efficiency in solving complex routing problems, which is crucial for industries relying on optimization.
Key Takeaways
- Introduces the TN-GEO framework for optimizing TSP using tensor networks.
- Employs a permutation-based formulation to ensure valid tour generation.
- Demonstrates improved performance over classical heuristics like 2-opt hill-climbing.
- Utilizes a k-site MPS variant for better modeling of local correlations.
- Experimental results validate the approach on benchmark instances with up to 52 cities.
Computer Science > Machine Learning arXiv:2602.20175 (cs) [Submitted on 12 Feb 2026] Title:Tensor Network Generator-Enhanced Optimization for Traveling Salesman Problem Authors:Ryo Sakai, Chen-Yu Liu View a PDF of the paper titled Tensor Network Generator-Enhanced Optimization for Traveling Salesman Problem, by Ryo Sakai and 1 other authors View PDF HTML (experimental) Abstract:We present an application of the tensor network generator-enhanced optimization (TN-GEO) framework to address the traveling salesman problem (TSP), a fundamental combinatorial optimization challenge. Our approach employs a tensor network Born machine based on automatically differentiable matrix product states (MPS) as the generative model, using the Born rule to define probability distributions over candidate solutions. Unlike approaches based on binary encoding, which require $N^2$ variables and penalty terms to enforce valid tour constraints, we adopt a permutation-based formulation with integer variables and use autoregressive sampling with masking to guarantee that every generated sample is a valid tour by construction. We also introduce a $k$-site MPS variant that learns distributions over $k$-grams (consecutive city subsequences) using a sliding window approach, enabling parameter-efficient modeling for larger instances. Experimental validation on TSPLIB benchmark instances with up to 52 cities demonstrates that TN-GEO can outperform classical heuristics including swap and 2-opt hill-climbing....