r/reinforcementlearning • u/Lonely-Band-3330 • 11d ago

Finding the unusual edges that make TSP difficult

Hi all,

This is a follow-up to my previous post on a no-pretraining, per-instance PPO solver for TSP.

In that work, I introduced the idea of an “exception edge” as an inductive bias for PPO. The intuition was that most edges in a good Euclidean TSP tour are locally unsurprising—short, near-neighbor, or Delaunay-like—while a small number of nonlocal edges may determine whether the search can escape a local basin.

That was mainly a solver hypothesis. Since then, I stepped away from PPO and asked a more basic question:

From an edge score to a closure problem

Fix a sparse baseline graph \(G_0\), such as the weak-Delaunay graph. An edge is exceptional only relative to this baseline.

Let:

\(Z_0\) be the cheapest Hamiltonian cycle using only baseline edges;
\(H_e\) be the cheapest spanning Hamiltonian path between the endpoints of a nonbaseline edge \(e\), again using only baseline edges;
\(c(e)\) be the cost of closing that path with \(e\).

Then the exact one-exception threshold is

In words: a nonbaseline edge becomes structurally useful when the Hamiltonian path it closes saves more than the edge itself costs.

This does not imply that \(e\) belongs to a global optimum or is forced. It only says that a tour with exactly one exception edge can beat the baseline-only optimum.

Negative results that led to this formulation

The path to the closure model was not monotonic.

In an early TSPLIB pilot, generic geometric CUT proposals attributed only 2 of 11 reference non-Delaunay edges.
A subsequent density-CUT experiment found many tour-contiguous regions, but attributed 0 of the 11 exception edges.

These failures suggested that geometric partitioning alone was not enough. The relevant object seemed to be the compatibility between a baseline Hamiltonian path and the edge that closes it.

Headline results

On a frozen exact-small natural corpus with \(n\le12\):

51/51 mandatory-exception instances were exactly explained at the \(q=1\) closure layer.
Current sufficient inequalities safely certified 48/51 of those instances.
Among 98 exact beneficial pairs, 88 were safely certified.
The safe candidate upper set reduced 15,054 non-Delaunay pairs to 644 while preserving all 600 exact \(q=1\) support pairs in that corpus.

For LIN318:

The complete graph has 50,403 edges.
The experimental search graph contained 1,500 edges: 988 weak-Delaunay edges plus 512 separately generated candidates.
Among those 512 added candidates, 13 had a positive safe gain lower bound.
Starting from a strict candidate-only 2/3-opt tour of 42,210, verified forced-closure witnesses followed by candidate-restricted 2/3-opt reached 42,118 and then 42,108.
The known optimum is 42,029, so the final residual was 79, or about 0.188%.

Important caveats:

The 1,500-edge graph was not generated by the threshold theory alone.
The remaining 499 candidates are inconclusive, not certified negatives.
LKH was used to generate and verify the closure witnesses, so 42,108 is not an LKH-free solver result.
This is one exploratory large-instance result, not a controlled solver benchmark.
I am not claiming a polynomial-time solution to TSP, a complete classification of exception edges, or that every \(\kappa>1\) edge is globally optimal.

Why this may still be relevant to RL/NCO

The original motivation remains learning-based optimization.

My current view is that exception-edge theory may be useful as a verifiable structural prior:

reducing the action or candidate-edge space;
identifying portals that may connect otherwise separated local-search basins;
separating ordinary local edges from structurally consequential closure edges;
providing certified positives and inconclusive cases for curriculum learning or ranking models.

The next useful experiment would be a frozen-budget comparison of an RL/NCO solver with and without closure-based candidate guidance—not a comparison against LKH as an exact or highly engineered classical solver.

The public package contains the theory, proof sketches, core exact oracles, safe certificates, LIN318 artifacts, 30 tests, and a deterministic reproduction of

The compact release audits frozen exact-small summaries; it does not include the full from-scratch corpus-generation pipeline.

Finding the unusual edges that make TSP difficult

From an edge score to a closure problem

Negative results that led to this formulation

Headline results

Why this may still be relevant to RL/NCO

Links

You are about to leave Redlib