Tensor Network Generator-Enhanced Optimization for Traveling Salesman Problem

• URL: http://arxiv.org/abs/2602.20175v1
• Date: Thu, 12 Feb 2026 21:18:19 GMT
• Title: Tensor Network Generator-Enhanced Optimization for Traveling Salesman Problem
• Authors: Ryo Sakai, Chen-Yu Liu,
• Abstract summary: We present an application of the tensor network generator-enhanced optimization (TN-GEO) framework to the traveling salesman problem (TSP)<n>Our approach employs a tensor network Born machine based on automatically differentiable matrix product states (MPS) as the generative model.<n>$k$-site variants, which put more focus on local correlations, show better results compared to the full-MPS case.
• Score: 12.04919729571293
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• 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. The $k$-site variants, which put more focus on local correlations, show better results compared to the full-MPS case.

Related papers

• Generative Diffusion Models for Resource Allocation in Wireless Networks [74.84410305593006]
  We train a policy to imitate an expert and generate new samples from the optimal distribution.<n>We achieve near-optimal performance through the sequential execution of the generated samples.<n>We present numerical results in a case study of power control.
  arXiv  Detail & Related papers  (2025-04-28T21:44:31Z)
• Combining Local Symmetry Exploitation and Reinforcement Learning for Optimised Probabilistic Inference -- A Work In Progress [2.2164989053903805]
  Efficient probabilistic inference by variable elimination in graphical models requires an optimal elimination order.<n>We adapt a reinforcement learning approach to find efficient contraction orders in tensor networks.<n>We show that leveraging specific structures during inference allows for introducing compact encodings of intermediate results.
  arXiv  Detail & Related papers  (2025-03-11T18:00:23Z)
• Regularized second-order optimization of tensor-network Born machines [2.8834278113855896]
  Born machines (TNBMs) are quantum-inspired generative models for learning data distributions.<n>A key bottleneck of TNBMs is the logarithmic nature of the loss function commonly used for this problem.<n>We present an improved second-order optimization technique for TNBM training, which significantly enhances convergence rates and the quality of the optimized model.
  arXiv  Detail & Related papers  (2025-01-30T19:00:04Z)
• Multi-view Bayesian optimisation in reduced dimension for engineering design [0.9626666671366836]
  We introduce a multi-view learning strategy that considers both the input design variables and output data representing the objective or constraint functions.<n>Adopting a fully probabilistic viewpoint, we use probabilistic partial least squares (PPLS) to learn an orthogonal mapping from the design variables to the latent variables.<n>We compare the proposed probabilistic partial least squares Bayesian optimisation (PPLS-BO) strategy to its deterministic counterpart, partial least squares Bayesian optimisation (PLS-BO), and classical Bayesian optimisation.
  arXiv  Detail & Related papers  (2025-01-02T22:03:00Z)
• Delta-AI: Local objectives for amortized inference in sparse graphical models [64.5938437823851]
  We present a new algorithm for amortized inference in sparse probabilistic graphical models (PGMs) Our approach is based on the observation that when the sampling of variables in a PGM is seen as a sequence of actions taken by an agent, sparsity of the PGM enables local credit assignment in the agent's policy learning objective. We illustrate $Delta$-AI's effectiveness for sampling from synthetic PGMs and training latent variable models with sparse factor structure.
  arXiv  Detail & Related papers  (2023-10-03T20:37:03Z)
• Stochastic Approximation Approaches to Group Distributionally Robust Optimization and Beyond [89.72693227960274]
  This paper investigates group distributionally robust optimization (GDRO) with the goal of learning a model that performs well over $m$ different distributions. To reduce the number of samples in each round from $m$ to 1, we cast GDRO as a two-player game, where one player conducts and the other executes an online algorithm for non-oblivious multi-armed bandits. In the second scenario, we propose to optimize the average top-$k$ risk instead of the maximum risk, thereby mitigating the impact of distributions.
  arXiv  Detail & Related papers  (2023-02-18T09:24:15Z)
• Symmetric Tensor Networks for Generative Modeling and Constrained Combinatorial Optimization [72.41480594026815]
  Constrained optimization problems abound in industry, from portfolio optimization to logistics. One of the major roadblocks in solving these problems is the presence of non-trivial hard constraints which limit the valid search space. In this work, we encode arbitrary integer-valued equality constraints of the form Ax=b, directly into U(1) symmetric networks (TNs) and leverage their applicability as quantum-inspired generative models.
  arXiv  Detail & Related papers  (2022-11-16T18:59:54Z)
• Transformers meet Stochastic Block Models: Attention with Data-Adaptive Sparsity and Cost [53.746169882193456]
  Recent works have proposed various sparse attention modules to overcome the quadratic cost of self-attention. We propose a model that resolves both problems by endowing each attention head with a mixed-membership Block Model. Our model outperforms previous efficient variants as well as the original Transformer with full attention.
  arXiv  Detail & Related papers  (2022-10-27T15:30:52Z)
• Federated Learning Using Variance Reduced Stochastic Gradient for Probabilistically Activated Agents [0.0]
  This paper proposes an algorithm for Federated Learning (FL) with a two-layer structure that achieves both variance reduction and a faster convergence rate to an optimal solution in the setting where each agent has an arbitrary probability of selection in each iteration.
  arXiv  Detail & Related papers  (2022-10-25T22:04:49Z)
• GEO: Enhancing Combinatorial Optimization with Classical and Quantum Generative Models [62.997667081978825]
  We introduce a new framework that leverages machine learning models known as generative models to solve optimization problems. We focus on a quantum-inspired version of GEO relying on tensor-network Born machines. We show its superior performance when the goal is to find the best minimum given a fixed budget for the number of function calls.
  arXiv  Detail & Related papers  (2021-01-15T18:18:38Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.