Tour Checker

What the lower-bound witness is

A tour is an upper bound: it shows what one valid order costs. The other half needs a number that no tour can beat. This page uses a 1-tree. Choose one root point, build a minimum spanning tree on every other point, then add the two cheapest edges at the root.

Node potentials alter an edge from c(i,j) to c(i,j) + pi(i) + pi(j). The page searches for useful potentials, but the search is not part of the proof. The copyable witness contains the potentials and a minimum 1-tree. Anyone can run Kruskal on the printed transformed costs, then subtract twice the sum of the potentials. That result is a valid lower bound.

The gap shown is (tour - bound) / bound. It is an upper limit on how much longer the pasted order can be than the true optimum, not a claim that the actual gap equals that percentage. When tour and bound meet, the feasibility certificate and lower-bound certificate together are a certificate of optimality.

How to check this yourself

1. Confirm that the printed labels and matrix are what you supplied. Mark each tour index once and add every consecutive cost, including last back to first.
2. Add the printed potential at each end of every edge. Ignore the root, sort the remaining edges, and run Kruskal until you have a spanning tree.
3. At the root, take the two least transformed edge costs. Add those to the tree, then subtract twice the sum of every potential.
4. Compare that lower bound with the tour total. If they meet, the tour is optimal. Otherwise divide their difference by the positive lower bound to reproduce the certified ceiling.

Limits

• The lower bound only applies to a symmetric round-trip problem. An asymmetric matrix still gets an independently summed tour cost, but no bound.
• Triangle inequality is not required. Exact non-negative integers and decimals are accepted.
• The lower-bound certificate and named baselines accept up to 200 points. Exact dynamic programming is capped at 16. On a deterministic dense test matrix in headless Chromium 149 on the build machine, this implementation took about 90 ms at 16 points and about 1.2 seconds at 19. Those are single runs on one desktop, quoted to the precision a single run supports, and nothing here re-checks them; the cap stays at 16 because a desktop measurement says nothing about a slower phone.
• The search for potentials is a heuristic, and it does not always reach the best bound that exists. The Held and Karp bound is the maximum of this bound over all potentials, and finding that maximum is itself an optimisation. What the certificate proves is that the potentials printed give the bound printed, which holds whether or not the search did well. It matters in practice: on both shipped fixtures the published optimal tour costs 937 and 1272, the true Held and Karp bound is those same numbers, and this page's search stops at 936 and 1271. So it reports "at most 0.107 per cent longer" about tours that are in fact optimal and could have been certified as such. That is an understatement of the tool's own strength, which is the safe direction to be wrong in, and it is stated here rather than left for a reader to discover.
• EUC_2D is a rounded integer convention. It is useful for drill paths, plotters, inspection points, and experiments. It is not unrounded geometry and it is not road distance.