Tensor Network Generator-Enhanced Optimization for Traveling Salesman Problem
This work addresses a fundamental combinatorial optimization problem for researchers in machine learning and operations research, but it is incremental as it adapts existing tensor network methods to a specific domain.
The authors tackled the traveling salesman problem by applying a tensor network generator-enhanced optimization framework, achieving results that outperform classical heuristics like swap and 2-opt hill-climbing on benchmark instances with up to 52 cities.
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. The $k$-site variants, which put more focus on local correlations, show better results compared to the full-MPS case.