A 93-Second Reproducible Certificate for the TSPLIB d2103 Optimum via HKD-Infinity Style Alternating Components and Weighted Hamiltonian Completion | IJCT Volume 13 – Issue 4 | IJCT-V13I4P1
International Journal of Computer Techniques
ISSN 2394-2231
Author
Michael S. Yang
Abstract
We report a reproducible certificate pipeline for the Euclidean TSPLIB instance d2103. Starting from a K=64 candidate graph and a stage-3 tour of length 81174, the method applies locally verifiable alternating edge components and a weighted Hamiltonian-completion connector ledger to obtain the known 80450 Hamiltonian tour. On a Mac M1/M2 run reported by the author, the complete internalized stage-1 through stage-4 harness required 71.111 seconds, while a subsequent checkpoint-to-certificate weighted replay required 21.732 seconds. The combined runtime is approximately 92.843 seconds. The final verifier reports
final cost = 80450, final subtours = 1, final bad degree = 0.
A vertex-by-vertex comparison against the supplied d2103 optimal-tour file shows 2103/2103 aligned vertex matches after rotation. The source code and the comparison CSV are included in the companion archive.
Keywords
Traveling Salesman Problem, TSPLIB, d2103, Euclidean TSP, certificate replay, al-ternating components, Hamiltonian completion, HKD-infinity.
Conclusion
The d2103 experiment demonstrates that a K=64 alternating-component and weighted Hamiltonian-completion certificate can reproduce the 80450 optimum in approximately 93 seconds end-to-end on the reported hard-ware. The final tour is validated by degree, cost, subtour count, K-nearest visibility, edge-set comparison, and vertex-by-vertex alignment to the supplied optimal tour. The result suggests that local ledger-balanced connector policies are a promising direction for further computational study of Euclidean TSP certificate construction.
References
[1]G. Reinelt, “TSPLIB–A Traveling Salesman Problem Library,” ORSA Journal on Computing, vol. 3, no. 4, pp. 376–384, 1991. See also TSPLIB95 documentation and instance files.
[2]D. L. Applegate, R. E. Bixby, V. Chvatal, and W. J. Cook, The Traveling Salesman Problem: A Com-putational Study. Princeton University Press, 2006.
[3]D. Applegate, R. E. Bixby, V. Chvatal, and W. J. Cook, “Concorde TSP Solver,” University of Waterloo TSP site and NEOS solver documentation.
[4]TSPLIB symmetric TSP data mirror and solutions file, https://github.com/mastqe/tsplib.
How to Cite This Paper
Michael S. Yang (2026). A 93-Second Reproducible Certificate for the TSPLIB d2103 Optimum via HKD-Infinity Style Alternating Components and Weighted Hamiltonian Completion. International Journal of Computer Techniques, 13(4). ISSN: 2394-2231.
