Three Correct TSP Solvers. Three Incompatible Promises.

The cold-chain fixture returns a 114-minute tour. The validated thermal window is 120 minutes.

Six minutes of margin.

The dispatcher asks a perfectly reasonable question:

Is 114 the best possible route?

For this run, the answer is not proven.

The tour came from Christofides with exact minimum-weight perfect matching. lvlath/tsp publishes ApproximationRatio=1.5 and Optimal=false.

The difference matters because the public call looks identical.

TL;DR

Tour and Cost are not enough for a production TSP result. In a 30-matrix experiment, 2-opt matched the exact optimum cost 24/30 times and 3-opt 27/30 times, yet neither solver can honestly publish Optimal=true. Christofides + Blossom matched the optimum only 8/30 times, but it is the heuristic regime with a formal 1.5 worst-case guarantee. Runtime, observed solution quality, and proof strength are different axes.

Textbooks explain permutations, NP-hardness, Branch-and-Bound, and 2-opt well enough. The awkward part appears later, when all of those algorithms are hidden behind one friendly function:

result, err := tsp.SolveMatrix(dist, ids, opts)

The call looks uniform. The result is not.

One result type, several very different claims

This is the public Result in github.com/lvlath/go@v0.1.0/tsp:

type Result struct {
    Tour  []int
    Cost  float64
    IDs   []string

    Algorithm Algorithm
    Exact     bool
    Optimal   bool
    TimedOut  bool

    MetricClosureApplied bool
    Symmetric             bool
    ApproximationRatio   float64

    Iterations    int
    NodesExpanded int
}

Those fields are intentionally redundant with the solver choice. A caller should not have to reconstruct what happened from old options, log text, or a function name.

A few valid states:

Route one: six minutes of cold-chain margin

The first runnable example is a six-stop symmetric metric travel-time matrix for vaccine distribution.

opts := tsp.DefaultOptions()
opts.Algo = tsp.Christofides
opts.Symmetric = true
opts.StartVertex = 0
opts.MatchingAlgo = tsp.BlossomMatch
opts.EnableLocalSearch = false

result, err := tsp.SolveMatrix(dist, nil, opts)

The relevant output is short:

route-minutes=114.0
formal-ratio=1.5
thermal-margin=6.0 minutes

The 114 is empirical: it belongs to this matrix and this returned tour.

The 1.5 comes from a theorem, and it survives only if the whole Christofides contract survives.

One caveat matters here: v0.1.0 documents metric input as a precondition; it does not prove the triangle inequality for every arbitrary matrix before solving. Symmetry and completeness can be validated mechanically. Metricity may still be a domain fact the caller has to defend. If that assumption is not trustworthy, the downstream system should not present 1.5 as an unconditional theorem.

The load-bearing stage here is minimum-weight perfect matching on the odd-degree vertices of the MST.

lvlath/tsp exposes that choice directly:

const (
    GreedyMatch MatchingAlgo = iota
    BlossomMatch
)

BlossomMatch is exact MWPM. GreedyMatch is deterministic and cheaper, but heuristic.

So this is a valid explicit configuration:

opts := tsp.DefaultOptions()
opts.Algo = tsp.Christofides
opts.Symmetric = true
opts.MatchingAlgo = tsp.GreedyMatch
opts.EnableLocalSearch = false

result, err := tsp.SolveMatrix(dist, ids, opts)
if err != nil {
    return err
}

fmt.Println(result.ApproximationRatio) // 0: no formal ratio claimed

There is no hidden "Blossom failed, quietly use Greedy" fallback. A failed stronger policy stays visible instead of returning weaker mathematics with stronger-looking metadata.

Route two: asymmetric cost is domain information

The second example models armored cash-in-transit routing. Cost combines time, fuel, guard exposure, and interception risk, so A -> B can legitimately differ from B -> A.

The solver is directed 2-opt*:

opts := tsp.DefaultOptions()
opts.Algo = tsp.TwoOptOnly
opts.Symmetric = false
opts.StartVertex = 0
opts.EnableLocalSearch = true

result, err := tsp.SolveMatrix(dist, nil, opts)

It returns:

directed-risk-cost=34.0
exact=false
optimal=false
approximation-ratio=0

The result is a deterministic locally improved ATSP tour under the selected policy. ApproximationRatio=0 states the missing guarantee explicitly instead of leaving the caller to infer it from Algorithm.

Route three: exact search can still return a non-optimal result

The semiconductor example has five drilling sites and an offline planning stage, so Branch-and-Bound with a 1-tree lower bound is a sensible exact choice:

opts := tsp.DefaultOptions()
opts.Algo = tsp.BranchAndBound
opts.Symmetric = true
opts.StartVertex = 0
opts.BoundAlgo = tsp.OneTreeBound
opts.EnableLocalSearch = false

result, err := tsp.SolveMatrix(dist, nil, opts)

The example completes with:

single-board-latency=16.8 ms
exact=true
optimal=true

Now add a wall-clock limit.

Branch-and-Bound is still an exact algorithm, but an interrupted search has not completed the proof. v0.1.0 may return a non-nil incumbent together with ErrTimeLimit:

result, err := tsp.SolveMatrix(dist, ids, opts)

if errors.Is(err, tsp.ErrTimeLimit) {
    if result == nil {
        return errors.New("time limit without incumbent")
    }

    fmt.Printf("cost=%.3f exact=%v optimal=%v timedOut=%v\n",
        result.Cost,
        result.Exact,    // true
        result.Optimal,  // false
        result.TimedOut, // true
    )
    return nil
}
if err != nil {
    return err
}

Exact describes the algorithm family. Optimal describes what this invocation actually proved.

That is a distinction a single Success bool cannot encode.

180 runs: observed quality vs. formal proof

For the article I generated 30 deterministic Euclidean metric matrices:

n = 8, 10, 12
10 fixed seeds per size

Each matrix was solved by six policies, for 180 solver runs. Held-Karp supplied the exact-cost baseline. Before writing a CSV row, an independent harness checked that the returned witness was a closed Hamiltonian cycle, visited every matrix vertex once, used finite non-negative edges, and recomputed the published cost from the source matrix.

I kept solution-quality measurements separate from testing.B: duration_ns in that CSV is diagnostic single-run timing, not benchmark evidence.

Across all 30 matrices:

This is where the experiment gets uncomfortable.

2-opt hit the exact optimum cost 24 times. Christofides + Blossom did it 8 times. Yet Christofides is the one allowed to publish a worst-case mathematical guarantee.

The apparent contradiction disappears once the two questions are separated:

• How did this solver behave on these 30 fixtures?
• What can the algorithm prove outside this sample?

The first is empirical evidence. The second is a theorem.

Treating "the route was close to the optimum in my benchmark" as a formal guarantee is benchmark-driven overfitting.

One matrix makes the distinction even sharper

The equal-size benchmark used the same deterministic n=10, seed-47 matrix for every solver. testing.B measured only SolveMatrix; fixture construction stayed outside the timed region.

The CSV for that exact fixture records:

Branch-and-Bound      cost=26037.596462281  nodes=3663  exact=true  optimal=true
2-opt                 cost=26037.596462281  iters=9     exact=false optimal=false
3-opt                 cost=26037.596462281  iters=0     exact=false optimal=false
Christofides/Blossom  cost=26404.536340990  ratio=1.5
Christofides/Greedy   cost=26404.536340990  ratio=0

The costs are identical, while the metadata differs because only the exact runs completed a proof of global optimality.

The equal-n table is a performance comparison for one fixed workload, not a universal solver ranking. That caveat matters: the permanent package benchmarks deliberately exercise very different regimes (n=12 Held-Karp, n=14 Branch-and-Bound, n=200 Christofides, n=500 2-opt), so putting those permanent numbers into one "fastest TSP algorithm" chart would be nonsense.

What does the 1.5 guarantee cost here?

The cleanest apples-to-apples regression pair in the package changes only the matching policy inside Christofides. Both use the same deterministic metric n=200 fixture. Local search is disabled.

On this machine and fixture, the exact-matching pipeline is about 26.4× slower, uses 6.2× the bytes per operation, and performs 6.4× the allocations.

This comparison is narrow enough to be useful: the outer algorithm, matrix family, size, and local-search setting stay fixed. The changed subroutine is also the one that carries the proof obligation.

The isolated dense Blossom benchmark makes the growth visible:

32 odd vertices   2.350 ms
64               12.36  ms
128              57.72  ms

From 32 to 128 odd vertices, measured solve time increased about 24.6× on this workload.

That does not make Greedy "better" or Blossom "slow". It tells me what the stronger matching policy costs in this implementation, on this machine, for these fixtures.

A claim-first way to choose the solver

A size-only rule is too vague for exact TSP. v0.1.0 ships Held-Karp with a soft MaxExactN guard whose default is 16. Callers may raise that option, but the underlying cost remains O(n²·2ⁿ) time and O(n·2ⁿ) memory. Branch-and-Bound has no comparable fixed vertex cap; its worst case is exponential and its practical limit depends on the matrix, lower bound, incumbent quality, and wall-clock budget.

goos: darwin
goarch: amd64
cpu: Intel(R) Core(TM) i9-9880H CPU @ 2.30GHz

GOMAXPROCS=1 go test ./tsp \
  -run '^$' \
  -bench 'Benchmark(HeldKarp|BranchBound)' \
  -benchmem -cpu=1 -count=10 -benchtime=3x

GOMAXPROCS=1 go test ./tsp \
  -run '^$' \
  -bench 'Benchmark(Christofides|TwoOpt|ThreeOpt)' \
  -benchmem -cpu=1 -count=10 -benchtime=1s

GOMAXPROCS=1 go test ./tsp \
  -run '^$' \
  -bench 'BenchmarkBlossom' \
  -benchmem -cpu=1 -count=10 -benchtime=1s

There was no single winner in these fixtures. Local search often matched the exact optimum cost; Christofides carried the stronger worst-case statement; exact methods were the only ones allowed to set Optimal=true. The benchmark and the theorem ranked the same solvers differently.

If a caller cannot distinguish proven, bounded, timed out, and merely good on this run, the solver is hiding state it already knows.

Code and contracts:

• TSP package
• Runnable scenarios
• Go Reference
• Long-form TSP documentation