8Z-RP
TSP as Compression

Four facts that should make you look harder at everything below.

2-opt is from 1958. Or-opt is from 1974. LZ complexity measurement, 1976. MDL, Rissanen 1978. XorShift PRNGs, edge-of-chaos dynamics, iterated local search — all well-established before 1995. There is nothing in this solver that requires hardware or theory invented after 1990.

The building blocks are ancient. What is new is the combination and the framing: “the shortest route is the one that compresses best” is not in any textbook. Using a complexity measurement to govern the search rather than merely analyze it is the second new thing. Not the parts. The wiring diagram.

This matters because the novelty pattern here — old parts, new architecture, breakthrough result — is exactly the kind of signal that future systems should learn to detect and study. The breakthroughs are not in the components. They are in the connections.

qa194 exact, DCC v2 vindication, and measured Rust acceleration.

qa194 and uy734 are official national TSP benchmark instances from the University of Waterloo World TSP / National TSP collection.

The shortest route is treated here as the route with the strongest compressive explanation.

That question changed the project. A shorter route tends to have more structure: fewer crossings, smoother geometry, tighter local relationships. More structure means more compressibility. 8Z already had a framework for searching structured explanations under strict cost. The TSP solver applies that same instinct to routes.

MDL acts as the judge: a move or route state only matters if it actually pays. DCC acts as the governor: it decides how hard to explore, when to exploit, when to switch tactics, and when the current search regime is stuck.

Measured: shorter tours are more compressible. The founding question holds.

The question “isn’t the shortest route the one compressed the best?” was axiomatic until March 2026. Then we measured it. Four workers from the uy734 run (n = 734, TSPLIB benchmark) each produced a different-quality tour. We computed LZ76 complexity of each tour’s city sequence and compared it with the tour’s optimality gap.

Spearman rank correlation ρ = +0.80 — higher gap correlates with higher LZ complexity. The direction is unambiguous: better tours compress better.

Why it works: a shorter tour connects nearby cities, creating spatial coherence in the visit sequence — repeating regional patterns that LZ76 captures. A longer tour has more cross-region jumps, making the sequence look more random and less compressible. The optimal tour sits on the compressible end of the spectrum, between maximally-ordered (sequential) and maximally-disordered (random permutation).

This is MDL made visible: the shortest description of the route and the shortest route itself point to the same object.

v2.6.5 · uy734 · 4 workers × 50 moves/n · Rust 2-opt · March 2026. First empirical measurement. Pending validation on 14-worker run for stronger statistical power.

From capped search to exact optimal — and beyond.

This was not one miracle run. The solver moved through a clear series of architectural steps, from v1.2.1 through v2.5.

The decisive move type was nearly excluded.

DCC auto-discovered that or-opt should dominate the kick budget — contradicting the default choice in classical ILS-TSP practice.

In the standard Iterated Local Search lineage for TSP, double-bridge is the canonical perturbation operator. It has been the default since at least the 1990s — used in Chained Lin-Kernighan (Applegate et al., 2003) and in Helsgaun’s LKH. Or-opt, by contrast, is traditionally a local search operator, not a perturbation. Using it as a kick is unconventional.

DCC v2 was given four kick types with equal initial weight: double-bridge, or-opt-1, or-opt-2, and or-opt-3. Nobody told it to prefer any of them. It measured improvements-per-move for each type and reallocated budget based on what was working. Here is what it found:

Rust 2-opt removed the main bottleneck. First time touching Rust.

Bojan had never written a line of Rust before March 13, 2026. Environment setup, PyO3 port, maturin build, 14-test determinism battery — done in hours alongside the solver work. The Rust module (zrp2opt, pyo3 0.27) is a drop-in replacement; the solver auto-detects it and falls back to pure Python if absent.

All matched runs preserve identical best tour lengths. Determinism verified across 13 test configurations.

Meta-DCC: the same algorithm governing the fleet that governs the search.

14 workers running independently waste compute. On nu3496 (3496 cities), the best worker found 2.02% gap while the worst sat at 4.34% — a 2,212-unit spread representing pure waste. The fix: a Level 1 DCC that monitors all workers, detects fleet stagnation, and (in Phase 2) intervenes by injecting good tours into stuck workers.

Same algorithm at both levels. The Meta-DCC uses the identical LZ76 compression sensor, coupling parameter, and escalation ladder as the base-level worker DCC. The only difference: what the sensor points at. Base-level DCC monitors individual search improvement streams. Meta-DCC monitors fleet-wide state snapshots. Same code. Same math. Different semantics.

The Fleet Lifecycle on uy734 (81 Meta-DCC Steps)

v2.5 ran 14 workers on uy734 (734 cities, optimal 79114) with Meta-DCC monitoring every 30 seconds. The resulting 81-step log revealed a clear three-phase lifecycle:

The Self-Calibrating Bands Discovery (P17)

v2.4 hardcoded the LZ compression thresholds at [0.25, 0.65]. Real fleet data lived at [0.01, 0.08] — off by 10×. meta_u drifted to floor and stayed there: useless signal. This was the same mistake as the or-opt exclusion — overriding the system instead of letting it learn.

v2.5 fixed it: self-calibrating bands. The system tracks its own LZ ratio history and derives thresholds from the 25th/75th percentiles of what it has actually observed. After a 10-observation warmup, bands converged to [0.040, 0.061]. meta_u then used its full range [3, 18] with 22 meaningful direction changes. The system that was built to let data decide now lets data decide about its own parameters. MDL all the way down.

Result: uy734 reached 0.46% gap (79478) with 14 workers in 40 minutes. Phase 1 is observer-only — workers are identical to v2.3. The value of v2.5 is diagnostic: for the first time, we can see fleet dynamics in real time and have a calibrated sensor for Phase 2 interventions.

The Eyes That Scale — GPU Changes Which Algorithm Wins.

Every paper on GPU + TSP does the same thing: take an existing operator (2-opt, 3-opt, genetic), parallelize its move evaluation on the GPU, and go faster. They speed up the legs of the solver. Nobody speeds up the eyes.

AIM³ Institute, Ljubljana · BD × AI Lab · March 2026

One human. Four AI systems. Neither alone could have done this.

Everyone says LLMs cannot invent or do novel things. Maybe true alone. But neither could the human do any of this alone. The result emerged from the interface, not from either side. This is a technical claim about how the work was produced, not modesty.

Explicit claim typing.

nu3496, Phase 2 tour injection, and the formal bridge.

17 days. One human. Four AI systems. Five solver versions. A research machine with public benchmark evidence.

The verified core: exact qa194, uy734 at 0.46%, DCC v2 vindication, auto-discovered operator preference, Rust acceleration, Meta-DCC fleet governance with self-calibrating bands, official benchmark provenance, and a clean architectural story connecting MDL, DCC, and route optimization. ~100× less code than the gold standard. All from a non-specialist who had never built a TSP solver before, collaborating with four AI systems under AIM³.

This is not a proof of P = NP. This is not a toy heuristic. This is a real research machine with public benchmark evidence, controller evidence, engineering evidence, and a controller that discovered what the experts defaulted past. The remarkable part is not that a heuristic can match a 200-city optimum — that has been possible for decades. The remarkable part is the way it was produced.