Certification of an optimal TSP tour through 85,900 cities

David L. Applegate, Robert E. Bixby, Vasek Chvatal, William Cook, Daniel G. Espinoza, Marcos Goycoolea, Keld Helsgaun

Research output: Contribution to journalJournal articleResearchpeer-review


We describe a computer code and data that together certify the optimality of a solution to the 85,900-city traveling salesman problem pla85900, the largest instance in the TSPLIB collection of challenge problems
Original languageEnglish
JournalOperations Research Letters
Issue number1
Pages (from-to)11-15
Number of pages6
Publication statusPublished - 2009


  • traveling salesman problem
  • integer programming
  • linear programming

Cite this

Applegate, D. L., Bixby, R. E., Chvatal, V., Cook, W., Espinoza, D. G., Goycoolea, M., & Helsgaun, K. (2009). Certification of an optimal TSP tour through 85,900 cities. Operations Research Letters, 37(1), 11-15. https://doi.org/10.1016/j.orl.2008.09.006