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

87 Scopus citations

Abstract

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
Volume37
Issue number1
DOIs
StatePublished - Jan 2009

Keywords

  • Integer programming
  • Linear programming
  • Traveling salesman problem

Fingerprint

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

Cite this