💻 computer science

Connected by Construction: Learning Tractable Near-Tour Marginals for Traveling Salesman Problems

The paper proposes C2TSP, an end-to-end unsupervised learning pipeline that directly learns interpretable Hamiltonian structures for the Traveling Salesman Problem through a connected-by-construction rooted 1-tree Gibbs family, achieving strong tour performance while preserving structural information via residual edge perturbations and certificate-guided sharpening.

Original authors: Ke Sun, Xinyuan Zhang, Xinwu Qian

Published 2026-07-15

📖 6 min read🧠 Deep dive

CC BY 4.0

Original authors: Ke Sun, Xinyuan Zhang, Xinwu Qian

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine you are trying to solve the ultimate delivery route puzzle: the Traveling Salesman Problem (TSP). You have a list of cities, and you need to find the shortest path that visits every single one exactly once and returns home. It's a classic brain teaser that gets incredibly hard as you add more cities.

For a long time, computer scientists have tried to teach machines to solve this using "learning-based" methods. Think of these methods like a student who is given a map and asked to guess the best route. But here's the catch: most of these students are actually guessing a "heat map" (a blurry picture showing which roads might be good) or a list of "construction rules" (how to build the route step-by-step). They don't actually hold the finished, connected loop in their hands until the very end, when they try to decode their guess into a real path. It's like trying to bake a cake by only guessing the ingredients and hoping the oven magically turns them into a perfect cake at the end.

The authors of this paper, Ke Sun, Xinyuan Zhang, and Xinwu Qian, say, "Wait a minute. If we don't know what the cake looks like before it goes in the oven, how do we know we're learning the right thing?"

The Big Idea: Building a Connected Skeleton First

Instead of guessing a blurry heat map, the authors propose a new way to learn called C2TSP. Their secret sauce is a concept they call "connected-by-construction."

Imagine you are building a model of a city's road network. Most methods try to draw lines on a piece of paper and hope they connect up later. C2TSP starts by building a specific, sturdy skeleton called a rooted 1-tree.

The Skeleton: Picture a central hub (the "root" city) connected to two roads. Then, imagine a tree of roads connecting all the other cities to that hub.
The Magic: By building it this way, the model is guaranteed to be connected. You can't accidentally draw a road that leads to nowhere or split the city into two islands. It's like building a house with a foundation that ensures the walls will always touch the roof.

The only thing this skeleton is missing to become a perfect tour (a Hamiltonian cycle) is that every city needs exactly two roads connected to it (one in, one out). In the 1-tree, the hub has two roads, but the other cities might have three or just one.

The Fix: The "Balancing Act" Layer

To fix the extra or missing roads, the team uses a clever trick they call a smoothed Held–Karp equilibration layer.

Think of this like a very smart traffic controller. The model looks at the 1-tree skeleton and asks, "Hey, City A has three roads, but it only needs two. City B has one, but needs two." The controller doesn't just delete roads; it adjusts the "prices" of the roads. It makes the extra roads expensive and the missing roads cheap, nudging the system until, on average, every city has exactly two roads.

This is a huge deal because, unlike other methods that try to guess the whole route at once, this method calculates the exact probability of every road being part of the solution while keeping the structure connected. They proved mathematically that they can do this calculation perfectly, which is something that was previously thought to be impossible for the full tour problem.

The "Certificate": A Safety Net

Even after the balancing act, there might still be a tiny bit of "mess" left. The skeleton is connected and balanced on average, but it might not be a perfect loop yet.

The authors introduce a certificate, which is like a safety net or a warning label. It measures exactly how much "mess" (or non-tour mass) is left in the system. It's a mathematical guarantee that says, "We know the structure is 99% there, and here is the exact number for the remaining 1%."

Using this certificate, they apply a final step called sharpening. Imagine you have a slightly fuzzy photo of a route. The sharpening step makes the good roads look super bright and the bad roads look dark, pushing the model closer to a perfect, crisp loop.

What They Found

The team tested their method on puzzles with 50, 100, 200, 500, and even 1,000 cities. Here is what the numbers showed:

Pure Decoding: When they let the model just pick the best route without any extra help (like a human fixing it up), C2TSP was incredibly strong. On a 100-city puzzle, it found a route with an optimality gap of just 1.90% after 100 rounds of local search, and 4.83% with just a simple "pick the best" guess.
Comparison: Other popular methods, like DIFUSCO or Fast-T2T, often struggled when the puzzles got big (500+ cities) unless they used a lot of extra search time. C2TSP stayed consistent.
The "Ablation" Test: To prove their ideas worked, they took parts of their system away.
- Without the edge perturbation (the part that learns to tweak road prices), the error jumped from 1.55% to 12.74%.
- Without the sharpening, the model learned a connected structure but didn't get as close to the perfect loop.
- This proves that both the learning of the road prices and the final sharpening step are necessary to get the best results.

What They Don't Claim

It's important to note what this paper doesn't say. They don't claim to have solved the Traveling Salesman Problem once and for all. They explicitly state that their method relies on a "tractable surrogate"—a smart approximation. The rooted 1-tree is a stand-in for the perfect tour. While it gets very close, the paper admits that the remaining "degree fluctuations" (the tiny imperfections where a city might have 3 roads instead of 2) are controlled and reduced, but not always eliminated exactly.

They also note that for very large puzzles (like 1,000 cities), some other methods that use a lot of local search (like DIMES) can still perform well, but C2TSP shines when you want a strong starting point that is already structurally sound.

The Takeaway

In simple terms, C2TSP is like teaching a robot to build a tour by first forcing it to build a connected skeleton, then teaching it to balance the roads, and finally giving it a certificate to check its work. Instead of guessing a blurry picture and hoping it turns into a route, the robot learns the shape of the route itself. The results suggest that this "connected-by-construction" approach makes the learning process more stable and the final routes much better, especially when the puzzles get big and complicated.

Technical Summary: Connected by Construction (C2TSP)

Problem Definition

The paper addresses the Traveling Salesman Problem (TSP), a canonical combinatorial optimization problem requiring a solution that satisfies two structural constraints: local degree constraints (every node must have degree two) and global connectivity (the selected edges must form a single Hamiltonian cycle).

Current learning-based methods for TSP often fail to represent this global connected structure directly within the learned object. Instead, they rely on:

Autoregressive construction: Generating tours sequentially with procedural masking.
Heatmap-based approaches: Predicting edge scores and relying on downstream repair, sampling, or search to obtain a valid tour.
Assignment-space relaxations: Modeling smooth permutation-like objects that do not directly capture the edge-adjacency structure determining tour cost.

These approaches suffer from two primary limitations: they do not provide a tractable global distribution over connected combinatorial objects, and their performance is tightly coupled with downstream decoding or search processes, making it difficult to separate the quality of the learned representation from the post-processing effects.

Methodology: C2TSP

The authors propose C2TSP (Connected by Construction), an end-to-end unsupervised learning pipeline that learns TSP through a structurally meaningful latent object: the rooted 1-tree.

1. The Rooted 1-Tree Surrogate

Instead of attempting to learn a Hamiltonian cycle directly (which has an intractable partition function), the model operates on the family of rooted 1-trees.

Definition: A rooted 1-tree consists of a spanning tree on all non-root nodes ( $\bar{V}$ ) plus exactly two edges incident to a fixed root node ( $r$ ).
Structural Guarantee: By construction, every configuration in this family is globally connected and satisfies the root degree constraint ( $d_r = 2$ ).
Tractability: Unlike the Hamiltonian Gibbs distribution, the rooted 1-tree Gibbs family admits an exact factorization. This allows for the exact computation of the partition function $Z_r(\eta)$ , edge marginals $\mu(\eta)$ , and degree moments, enabling expected-cost training without sampling.

2. Smoothed Held–Karp Equilibration

The primary structural defect of a rooted 1-tree is that non-root nodes may not have degree two. To correct this, the authors introduce a smoothed Held–Karp (HK) equilibration layer.

This layer solves for node-additive dual variables ( $\lambda$ ) that tilt the edge costs such that the expected degree of every non-root node equals two under the modified Gibbs distribution.
The layer is trained end-to-end using implicit differentiation through the equilibrium map, following the paradigm of implicit optimization layers.
This process ensures the learned distribution is degree-balanced in expectation, removing the "degree defect" while maintaining connectivity.

3. Certificate-Guided Sharpening

Even after HK equilibration, the distribution may still contain probability mass on non-tour structures (rooted 1-trees that are not Hamiltonian cycles).

Certificate: The authors derive a certificate that upper-bounds this "non-tour mass" ( $\gamma(q)$ ) using the total variance of the non-root degrees: $\gamma(q) \leq \frac{1}{2} \sum \text{Var}(d_i)$ .
Refinement: A certificate-guided sharpening step uses the derivative of a Bernoulli upper-bound certificate to push the marginal distribution toward more tour-like structures. This acts as a deterministic refinement that penalizes low-probability edges and rewards high-probability edges, reducing the certified upper bound on non-tour mass.

4. Learning Pipeline

The pipeline learns residual edge perturbations ( $\Gamma_\theta$ ) from the unbiased TSP cost.

Forward Pass: Raw costs are perturbed, projected to remove node-additive components, passed through the HK equilibration layer, and refined via certificate-guided sharpening.
Loss Function: The model is trained using an unsupervised loss based on the expected TSP cost of the learned edge marginals, without explicit penalty terms for structural constraints (as these are enforced by the architecture).

Key Contributions

Tractable Rooted 1-Tree Representation: The paper introduces a representation that ensures global connectivity by construction while admitting exact marginal computation for training.
C2TSP Pipeline: An end-to-end unsupervised framework combining a Graph Neural Network (GNN) for residual edge perturbation and a smoothed Held–Karp layer for degree equilibration.
Non-Tour Mass Certificate: The derivation of a certificate bounding the residual structural gap, which is then used to guide a sharpening mechanism that pushes the distribution toward Hamiltonian cycles.
Empirical Validation: Demonstration that the rooted 1-tree representation yields strong pure-decoding performance and remains robust when integrated into classical solvers like LKH-3, unlike several heatmap-based baselines that degrade at larger scales.

Experimental Results

The authors evaluated C2TSP on 2-D symmetric Euclidean TSP instances (TSP-50 to TSP-1000) against baselines including DIFUSCO, DIMES, Fast-T2T, UTSP, and NeuroLKH.

Pure Decoding: C2TSP achieved the lowest optimality gap in 20 out of 25 tested configurations (varying problem size and decoder level). Notably, it performed best in regimes with heavy local search budgets (e.g., 100 iterations of 2-opt), suggesting the learned distribution already encodes strong tour-like structure.
LKH Integration: When used as a candidate source for the LKH-3 solver, C2TSP remained robust across all problem sizes, staying within $\sim 1$ part per ten thousand (‱) of vanilla LKH-3. In contrast, heatmap-based methods (DIFUSCO, Fast-T2T, UTSP) degraded significantly at larger sizes ( $n \geq 500$ ) when integrated with LKH.
Ablation Studies:
- Removing edge perturbation caused a substantial performance drop (average gap increased from 1.55% to 12.74%), indicating the necessity of learning the residual edge geometry.
- Certificate-guided sharpening further improved performance by refining the marginal distribution, confirming that low relaxed cost alone is insufficient for high-quality decoding.

Significance and Claims

The paper claims that the differentiable latent object is a central modeling choice for learning-based TSP. By encoding connectedness before decoding, C2TSP exposes a "near-tour marginal" whose structural evolution can be trained, certified, and analyzed.

The authors position their work as a shift from learning unconstrained edge scores to learning a tractable near-tour marginal with explicit structural meaning. They argue that this approach separates the learned representation from post-processing, allowing the model to provide a globally consistent starting point for local search procedures.

The paper acknowledges a limitation inherent to its design choice: the rooted 1-tree relaxes the exact Hamiltonian-cycle support. While connectivity is enforced and degree balance is restored in expectation, the remaining degree fluctuations are controlled via equilibration and sharpening rather than eliminated exactly. The authors suggest this opens directions for tighter certificate-directed updates and richer tractable connected families.