Tensor-Network Formulation of the Traveling Salesman Problem and Variants

This paper introduces a tensor-network formulation for the Traveling Salesman Problem and its variants that uses Boltzmann-weighted layers and counting filters to identify optimal tours via a sequential marginal rule, serving as a heuristic for small-scale industrial applications rather than a superior alternative to specialized classical solvers.

The Gist

The Big Picture: Solving the "Traveling Salesman" Puzzle with a New Kind of Calculator

Imagine you are a traveling salesperson. You have a map with 10, 20, or even 100 cities. You need to visit every single city exactly once and return home, but you want to do it in the shortest possible distance to save gas and time. This is the famous Traveling Salesman Problem (TSP).

The problem is that as you add more cities, the number of possible routes explodes. It's like trying to find the perfect key in a pile of keys that grows so fast that checking every single one would take longer than the age of the universe. This is why computers struggle with it.

This paper introduces a new way to tackle this problem using Tensor Networks. Think of a Tensor Network not as a computer program, but as a giant, multi-layered filter system.

The Analogy: The "Gold Dust" Sifter

Imagine you have a giant bag of sand mixed with gold dust.

• The Sand: Represents all the bad, long, inefficient routes.
• The Gold: Represents the perfect, shortest route.
• The Goal: You want to separate the gold from the sand without looking at every single grain individually.

The authors built a machine (the Tensor Network) to do this:

1. The Initial Mix (The Superposition): First, the machine creates a "superposition." Imagine it magically creates a copy of every possible route at the same time. It's like having a million different versions of yourself, each taking a different path.
2. The Weighting (The Heat): Next, the machine applies a "temperature" (called $\tau$). Think of this as a heat lamp.
   • The long, inefficient routes (the sand) get hot and turn into light, fading away.
   • The short, efficient routes (the gold) stay cool and heavy.
   • The machine uses math (Boltzmann factors) to make the bad routes disappear faster than the good ones.
3. The Filters (The Rules): This is the most important part. You can't just have any route; you can't visit the same city twice. The authors built special Counting Filters.
   • Imagine a security guard at every city. If a traveler tries to visit a city they've already been to, the guard slams the door shut on that specific route.
   • These filters are "sparse," meaning they are very efficient at blocking the wrong paths without needing to check every single possibility manually.
4. The Result (The Marginal): After passing through the heat and the filters, the machine squeezes everything down. It asks, "If I look at the first city, which one is the most likely to be part of the winning route?" It picks that one, locks it in, and then repeats the process for the second city, and so on, until the whole route is built.

What They Actually Did (The Experiments)

The authors didn't claim this method is a magic bullet that solves every problem instantly. They were very honest about its limits.

• Small Tests: They tested their method on small maps (5 to 12 cities).
• Calibration: They found that the "temperature" setting ($\tau$) is crucial. If it's too low, the bad routes don't fade away enough. If it's too high, the computer gets confused by tiny math errors. They had to carefully tune this setting for each map size.
• The Results:
  • When they tuned the settings perfectly, their method found the perfect route about 95% of the time on these small maps.
  • When they compared it to standard computer methods (like "Greedy" or "Simulated Annealing"), their method was often better at finding the perfect route.
  • However, they admitted that for very large maps, the math still gets too heavy (exponential complexity), just like the old methods. It's not a "polynomial time" miracle; it's just a different, very structured way of doing the math.

Real-World Test: The Job Reassignment Problem

To see if this works outside of theory, they applied it to a real industrial problem for ONCE (a Spanish organization for the blind).

• The Problem: They had workers assigned to jobs and some empty jobs. They needed to see if moving a worker to a new job would make the whole team more productive.
• The Twist: This isn't exactly a "traveling" problem, but it's similar: you have to assign unique jobs to unique people without double-booking.
• The Outcome: They compared their Tensor Network method against two other powerful tools (a quantum annealer and a digital annealer).
  • The results were identical in terms of total productivity gain.
  • The only differences were in "tie-breaking" situations where two options were mathematically equal; the machines just picked different ones randomly.
  • Conclusion: This proved their method works in the real world and can be integrated into industrial software, even if it doesn't beat the specialized tools at this specific task.

The Bottom Line

The paper presents a new mathematical toolkit for solving routing and assignment puzzles.

• The Good: It offers a very clear, modular way to handle complex rules (like "don't visit the same city twice") and can find perfect solutions on small problems. It's like having a highly organized, rule-following assistant that never gets tired of checking constraints.
• The Bad: It doesn't magically make huge problems easy. The math still gets exponentially harder as the problem grows. It requires careful tuning (calibration) to work well.
• The Takeaway: It's a powerful new way to think about these problems and a solid tool for specific, smaller-scale industrial tasks, but it is not a replacement for all existing super-fast solvers yet.

In short: They built a sophisticated sieve that can filter out bad routes and find the best one, but you still have to feed it the right settings to get the gold.

Technical Summary

Technical Summary: Tensor-Network Formulation of the Traveling Salesman Problem and Variants

Problem Definition
The paper addresses the Traveling Salesman Problem (TSP) and several of its generalizations, including the Time-Dependent TSP (TDTSP), Job Reassignment Problem (JRP), and variants involving non-repetition constraints, precedence rules, group constraints, and bottleneck objectives. The TSP is defined as finding the shortest route visiting $N$ nodes exactly once and returning to the start, a known NP-hard problem. While exact algorithms like Held-Karp ($O(N^2 2^N)$) and branch-and-bound exist, they face exponential complexity that limits their scalability for industrial cases. Conversely, heuristics (e.g., genetic algorithms, local search) offer approximate solutions without optimality guarantees. The authors note that emerging quantum algorithms (QAOA, VQE) are currently limited by hardware noise (NISQ era), motivating the exploration of classical techniques that mimic quantum system properties.

Methodology
The core contribution is a tensor-network (TN) formulation that represents candidate tours as states in a tensor product space. The method operates through three primary mechanisms:

1. Tensor Network Construction:

   • Initialization ('+'): Creates a uniform superposition of all possible node assignments for each time step.
   • Optimization ('S'): Applies an imaginary time evolution operator $U = e^{-\tau C(\vec{y})}$, where $\tau$ is a damping factor and $C(\vec{y})$ is the tour cost. This exponentially suppresses high-cost configurations, analogous to finding the ground state in quantum systems.
   • Constraint Filtering ('F'): Introduces Matrix Product Operator (MPO) layers to enforce constraints. For the standard TSP, these layers act as counting filters ensuring each node appears exactly once. The filters utilize binary bond indices to track whether a specific node has been visited, effectively implementing the Levi-Civita symbol constraint $|\epsilon_{y_0, \dots, y_{\hat{N}-1}}|^2$.
   • Extraction ('+'): A trace layer sums the amplitudes to produce marginal weights.

2. Sequential Marginal Extraction:
   The solution is extracted iteratively. For a fixed prefix of the tour, the algorithm computes the marginal weight $Z_p(a; \tau)$ for each candidate node $a$ at the next position. In the limit of $\tau \to \infty$ and exact arithmetic, the node maximizing this weight is guaranteed to be part of an optimal tour (Proposition 3.2). The algorithm selects the maximizing node, updates the prefix, and repeats until the tour is complete.

3. Generalizations:
   The framework is adapted for various TSP variants by modifying the filter and evolution layers:

   • DNSNN (Different Number of Steps/Nodes): Filters allow nodes to appear between $N^0$ and $N^f$ times.
   • NMTSP (Non-Markovian): Uses higher-order MPOs to handle costs dependent on $K$ previous steps.
   • BTSP (Bottleneck): Replaces the cost evolution with a layer tracking the maximum edge cost encountered.
   • PTSP (Group-Constrained): Filters enforce visiting exactly one node per class.
   • TSPP (Precedence): Local projectors suppress nodes if their required predecessors have not yet appeared.
   • JRP (Job Reassignment): Modeled as a linear assignment problem where a "no-move" state is repeatable, and specific vacancies are unique.

4. Approximation and Complexity:
   The exact contraction of the full tensor network is exponential, scaling as $O(\hat{N}^4 2^{\hat{N}})$ for dense layer-wise contraction. To address larger instances, the authors propose:

   • Layer Ablation: Applying only a subset of constraint layers to reduce complexity, treating the result as a heuristic.
   • Sparse-Local Contraction: Exploiting the deterministic, sparse nature of the local filter tensors to reduce polynomial prefactors (e.g., from $O(\hat{N}^4 2^{\hat{N}})$ to $O(\hat{N}^3 2^{\hat{N}})$) without changing the exponential scaling.
   • Finite-$\tau$ Heuristic: Using finite precision and finite $\tau$ to approximate the zero-temperature limit, acknowledging that numerical contrast and degeneracies affect solution quality.

Key Contributions

• Explicit Marginal Formula: Derivation of a tensor-network marginal equation whose zero-temperature, exact-arithmetic limit identifies an optimal feasible tour via a sequential marginal rule.
• Constraint Encoding: Definition of MPO layers for counting constraints (non-repetition) applicable to various combinatorial problems.
• Generalization Framework: A modular construction adapting the TN formalism to TSP variants (TDTSP, JRP, BTSP, etc.) by altering specific tensor layers.
• Heuristic Implementation: A finite-precision, finite-$\tau$ implementation that functions as a calibrated heuristic, with an analysis of its behavior regarding numerical contrast and degeneracy.

Results
The experimental study focuses on small, synthetic instances ($N \in \{5, \dots, 12\}$) to validate the method's correctness and numerical behavior rather than to claim computational superiority over specialized solvers.

• Calibration: The imaginary-time parameter $\tau$ is size-dependent. A calibration sweep ($\tau \in \{1, \dots, 40\}$) significantly improved the optimal-solution rate from 55.56% (at $\tau=1$) to 95.56% on the evaluation set.
• Solver Comparison: On small instances, the calibrated TN solver achieved a 95.24% optimality rate, outperforming NetworkX greedy (26.67%) and simulated annealing (59.05%), but falling short of the exact Held-Karp reference (100%).
• Layer Ablation: Removing constraint layers degraded solution quality, confirming that the full filter set is necessary for high accuracy.
• Industrial Case (JRP): In a proof-of-concept for the ONCE Job Reassignment Problem, the TN method produced solutions with accumulated costs identical to the Azure Digital Annealer, differing only in degenerate cases where multiple optimal assignments exist.

Significance and Claims
The authors explicitly state modesty regarding the method's computational power. They do not claim a general computational advantage over specialized classical solvers (like Held-Karp, branch-and-cut, or assignment-specific algorithms) for the general TSP.

• Formal Representation: The work is presented as a "formal exact-arithmetic exponential-time representation" and a "platform for controlled approximations and extensions."
• Heuristic Nature: The finite-$\tau$ implementation is characterized as a "calibrated finite-precision heuristic" whose behavior depends on numerical contrast and degeneracies.
• Utility: The primary value lies in the modular tensor-network framework, which allows for the systematic integration of diverse constraints (precedence, groups, non-Markovian costs) and the application of approximation techniques (layer removal, sparse contractions) within a unified formalism.
• Limitations: The method retains exponential scaling in the worst case. Numerical stability issues (underflow, loss of contrast in degenerate cases) and the need for size-dependent calibration are identified as significant limitations.

In summary, the paper provides a rigorous tensor-network formalism for TSP and its variants, demonstrating its ability to recover optimal solutions on small instances and integrate industrial constraints, while acknowledging that it does not overcome the fundamental exponential complexity of the problem.