Certification of an optimal TSP tour through 85,900 cities

David L. Applegate, Robert E. Bixby, Vašek Chvátal, William Cook, Daniel G. Espinoza, Marcos Goycoolea, Keld Helsgaun

Research output: Contribution to journalArticlepeer-review

110 Scopus citations


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
Pages (from-to)11-15
Number of pages5
JournalOperations Research Letters
Issue number1
StatePublished - Jan 2009


  • Integer programming
  • Linear programming
  • Traveling salesman problem


Dive into the research topics of 'Certification of an optimal TSP tour through 85,900 cities'. Together they form a unique fingerprint.

Cite this