Cracking TSP: A Closure Theory for Identifying Critical "Exception Edges"

The Traveling Salesman Problem (TSP) is one of the most classic and challenging NP-hard problems in combinatorial optimization. TSP requires finding the shortest route that visits all given cities exactly once and returns to the starting point. For n cities, the number of possible routes is (n-1)!/2 — even for n=20, this exceeds 10^16 possibilities. No known polynomial-time exact algorithm can solve this problem in all cases, and the best exact methods (such as the branch-and-bound with cutting planes used by the Concorde solver) still require exponential time in the worst case. In Euclidean TSP — where cities lie on a Euclidean plane and edge weights are Euclidean distances — most edges in optimal tours are "locally reasonable": they connect nearby nodes and align with the intuition of Delaunay triangulation.

Delaunay triangulation is a core construction in computational geometry: given a set of points in the plane, it constructs a triangulation such that no point falls inside the circumscribed circle of any other triangle. This property means Delaunay edges tend to connect pairs of points that are "natural neighbors." Research shows that for randomly uniformly distributed point sets, over 95% of edges in optimal TSP solutions belong to the Delaunay triangulation. However, what truly makes TSP difficult is often the remaining few "unusual" edges. Recently, a researcher published an exploratory work on Reddit attempting to mathematically characterize these "exception edges" precisely, providing verifiable structural priors for reinforcement learning (RL) and neural combinatorial optimization (NCO) solvers.

From Solver Intuition to the Closure Problem

This research is a continuation of the author's earlier work. In a previous "no-pretraining, per-instance PPO solver," the author introduced the concept of "exception edges" as an inductive bias for PPO. Proximal Policy Optimization (PPO) is a policy gradient reinforcement learning algorithm proposed by OpenAI in 2017 that constrains policy update magnitude through a clipped objective function, balancing training stability with sample efficiency. In neural combinatorial optimization, RL is used to train neural networks to directly construct or improve solutions to combinatorial optimization problems. Typical paradigms include autoregressive construction (sequentially selecting the next city to visit) and improvement methods (learning selection strategies for local search operators). "Per-instance PPO" refers to training a policy network from scratch for each specific problem instance, avoiding out-of-distribution generalization issues but at higher computational cost.

The core intuition is: in a good Euclidean TSP tour, the vast majority of edges are short, connect nearby neighbors, resemble Delaunay edges, and are "locally unremarkable"; while a few non-local edges may determine whether the search can escape the "basins" of local optima. In combinatorial optimization, the "basin" structure of the search space describes which initial solutions will ultimately converge to the same local optimum — solutions within the same basin can reach each other through local moves, while "barriers" between basins represent regions where solution quality must temporarily worsen to cross. Exception edges may span exactly between two basins, providing "shortcuts" from one local optimum to a better one.

But this was initially just a solver-level hypothesis. Afterward, the author set aside PPO and pursued a more fundamental question: can we mathematically define what an "exception edge" is? The answer was to reformulate it as a closure problem.

In graph theory and combinatorial optimization, closure problems typically refer to finding maximum-weight closed subsets in directed graphs. The meaning of "closure" in this paper is different: it refers to using an edge to "close" a Hamiltonian path into a Hamiltonian circuit — given a Hamiltonian path between two endpoints (a path visiting all nodes exactly once), adding the edge connecting these two endpoints forms a complete Hamiltonian circuit. This operation transforms "whether to use a certain non-standard edge" into a precise cost comparison problem.

Precise Definition of the Exception Threshold

The author fixes a sparse reference graph $G_0$ (e.g., a weak Delaunay graph), and whether an edge is "exceptional" is defined only relative to this reference. A weak Delaunay graph is a relaxed version of Delaunay triangulation that allows degenerate cases where points lie exactly on circumscribed circles, typically containing more edges than strict Delaunay graphs. The specific definition is as follows:

• $Z_0$: the cheapest Hamiltonian circuit using only reference edges;
• $H_e$: for a non-reference edge $e$, the cheapest spanning Hamiltonian path connecting its two endpoints using only reference edges;
• $c(e)$: the cost of closing that path with edge $e$.

This yields a precise "single-exception threshold": when a non-reference edge closes a Hamiltonian path with cost savings exceeding the edge's own cost, that edge becomes structurally useful. In other words, a tour containing exactly one exception edge can beat the optimal solution using only reference edges. Mathematically, this is equivalent to $\text{cost}(H_e) + c(e) < Z_0$, meaning the total length of the closed circuit is strictly less than the optimal circuit using only reference edges.

Interestingly, this does not mean $e$ necessarily belongs to the global optimum, nor that it is forced to be included. It simply reveals that this edge has "structural value" — it breaks the optimality barrier achievable using only "conventional" edges.

Key Insights Revealed by Negative Results

The path to the closure model was not smooth. The author candidly shared several failed attempts, which is precisely what demonstrates the rigor of this work.

In early TSPLIB pilots, a generic geometric CUT proposal method could explain only 2 out of 11 reference non-Delaunay edges. Subsequent density-CUT experiments discovered many path-contiguous regions but achieved an explanation rate of 0 for those 11 exception edges.

These failures convey a clear signal: geometric partitioning alone is insufficient. The truly critical factor is the "compatibility" between the reference Hamiltonian path and the edge that closes it. This realization ultimately gave rise to the closure model approach — the essence of the problem lies not in geometric position, but in the cost trade-off between path and closing edge. This means one cannot judge whether an edge is "exceptional" solely based on its length, angle, or the geometric region it spans — one must consider how the entire path structure cooperates with that edge.

Core Experimental Validation

The author validated the theory's effectiveness at two levels.

Small-Scale Exact Corpus Validation

On a frozen exact small-scale natural corpus with $n \le 12$:

• 51/51 "forced exception" instances were precisely explained at the $q=1$ closure layer;
• The current sufficient inequality safely certified 48/51 of these instances;
• Of 98 exact beneficial pairs, 88 were safely certified;
• The safe candidate superset compressed 15,054 non-Delaunay pairs down to 644, while retaining all 600 exact $q=1$ support pairs in the corpus.

This means the method can drastically reduce the candidate space while losing no critical structural information — compressing candidate edges from 15,054 to 644 (a compression ratio exceeding 23:1) with zero omissions of all truly useful edges. This is extremely valuable for TSP solvers, as candidate set size directly determines the computational complexity of search algorithms.

Large-Scale Instance LIN318 Validation

For the classic LIN318 instance (complete graph with 50,403 edges) — a 318-city instance from the TSPLIB benchmark library proposed by Lin and Kernighan in 1973, with a known optimal tour length of 42,029:

• The experimental search graph contained only 1,500 edges: 988 weak Delaunay edges plus 512 independently generated candidate edges;
• Among the 512 candidate edges, 13 had positive "safe gain lower bounds";
• Starting from a strictly candidate-restricted 2/3-opt tour (length 42,210), through verified forced closure witnesses, followed by candidate-restricted 2/3-opt optimization, the final result reached 42,108;
• The known optimum is 42,029, with a final residual of only 79, approximately 0.188%.

Here, 2-opt and 3-opt are classic local search operators in TSP: 2-opt removes two edges from the tour and reconnects in another way (essentially reversing a sub-segment of the path), while 3-opt removes three edges with multiple reconnection possibilities. "Candidate-restricted" means only considering edges from a predefined candidate set for exchanges, reducing per-step search computation from O(n²) or O(n³) dramatically, though potentially missing some improvements. Achieving a 0.188% residual on a search graph compressed from 50,403 to 1,500 edges demonstrates the enormous potential of structural priors in reducing search space.

Honest Acknowledgment of Limitations

The author maintained a high degree of clarity about the boundaries of this work. He explicitly stated:

• The 1,500-edge search graph was not generated entirely by threshold theory;
• The remaining 499 candidates are "indeterminate" rather than certified negatives;
• LKH was used to generate and verify closure witnesses, so 42,108 is not an "LKH-free" independent solving result;
• This is an exploratory large-scale experiment, not a controlled solver benchmark.

LKH (Lin-Kernighan-Helsgott) is a TSP solver developed by Keld Helsgott, widely regarded as one of the most powerful TSP heuristic algorithms in practice. Through sophisticated k-opt moves and carefully designed candidate edge generation strategies, it can find near-optimal or even optimal solutions in reasonable time. The author's reliance on LKH in experiments means the results validate the theoretical framework's soundness but cannot prove that the framework can independently replace powerful solvers.

He repeatedly emphasized: no claim of polynomial-time TSP solving, no claim of complete classification of exception edges, and no claim that every edge with $\kappa>1$ belongs to the global optimum.

Potential Implications for Reinforcement Learning and Neural Combinatorial Optimization

The original motivation for this work has always been learning-based combinatorial optimization. Neural combinatorial optimization (NCO) is a research direction that has emerged in recent years, attempting to use deep learning models (such as Transformers, graph neural networks) to directly learn solving strategies for combinatorial optimization problems. Representative works include Pointer Network, Attention Model (AM), POMO, and others. One of the core challenges for these methods is how to effectively leverage structural properties of problems — purely end-to-end learning often struggles to discover deep combinatorial structures.

The author believes exception edge theory can serve as a verifiable structural prior, contributing in the following ways:

• Reducing action space or candidate edge space, allowing RL agents to learn in a smaller search space — this directly alleviates combinatorial explosion, as action space shrinks from O(n²) scale to proportional to candidate set size;
• Identifying "portals" — edges that may connect otherwise isolated local search basins — this provides explicit directional guidance for RL exploration strategies, avoiding ineffective sampling within the same basin;
• Distinguishing ordinary local edges from structurally critical closure edges — this can be translated into prior weights in attention mechanisms or edge features in graph neural networks;
• Providing certified positive examples and indeterminate cases for curriculum learning or ranking models — curriculum learning arranges training samples from easy to hard, and closure theory naturally provides difficulty grading.

The author's suggested next experiment is to compare RL/NCO solver performance "with" versus "without" closure-based candidate guidance under a frozen budget — rather than directly competing against the highly engineered classical solver LKH. This is a pragmatic experimental design: rather than trying to prove learning methods can beat decades of engineering optimization in classical methods, it verifies whether structural priors can deliver substantial improvements for learning methods under fixed computational budgets.

Conclusion and Open Questions

The author has publicly released on GitHub the complete theory, proof sketches, core exact oracles, safety certificates, LIN318 experimental artifacts, and 30 tests, with deterministic reproduction. He specifically hopes the community will provide feedback on three questions:

1. Has this Hamiltonian closure formalization been studied under other names?
2. Are there stronger computable lower bounds for endpoint-constrained Hamiltonian paths $H_e$?
3. Is closure-based candidate guidance more suitable as an inductive bias for RL/NCO, or should it serve purely as a classical candidate generation method?

The second question is particularly noteworthy: if tighter lower bounds can be found (such as relaxation-based LP lower bounds or 1-tree lower bounds), candidate edges could be filtered more precisely without solving NP-hard subproblems. The third question touches on a deeper debate — whether structural knowledge should be "hardcoded" into algorithms or left for learners to discover on their own.

The value of this research may lie not in what it "solves," but in providing a verifiable new perspective for understanding TSP's "sources of difficulty" in a rigorous and honest manner — transforming the elusive question of "which edges matter" into a precisely computable cost trade-off problem. It suggests a possible research path: guiding learning through understanding problem structure, rather than hoping purely end-to-end learning will automatically discover all structure.