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

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
JournalOperations Research Letters
Volume37
Issue number1
Pages (from-to)11-15
Number of pages6
ISSN0167-6377
DOIs
Publication statusPublished - 2009

Keywords

  • 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
Applegate, David L. ; Bixby, Robert E. ; Chvatal, Vasek ; Cook, William ; Espinoza, Daniel G. ; Goycoolea, Marcos ; Helsgaun, Keld. / Certification of an optimal TSP tour through 85,900 cities. In: Operations Research Letters. 2009 ; Vol. 37, No. 1. pp. 11-15.
@article{67a09ff0c2a311dc9a79000ea68e967b,
title = "Certification of an optimal TSP tour through 85,900 cities",
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",
keywords = "traveling salesman problem, integer programming, linear programming",
author = "Applegate, {David L.} and Bixby, {Robert E.} and Vasek Chvatal and William Cook and Espinoza, {Daniel G.} and Marcos Goycoolea and Keld Helsgaun",
year = "2009",
doi = "10.1016/j.orl.2008.09.006",
language = "English",
volume = "37",
pages = "11--15",
journal = "Operations Research Letters",
issn = "0167-6377",
publisher = "Elsevier BV",
number = "1",

}

Applegate, DL, Bixby, RE, Chvatal, V, Cook, W, Espinoza, DG, Goycoolea, M & Helsgaun, K 2009, 'Certification of an optimal TSP tour through 85,900 cities' Operations Research Letters, vol. 37, no. 1, pp. 11-15. https://doi.org/10.1016/j.orl.2008.09.006

Certification of an optimal TSP tour through 85,900 cities. / Applegate, David L.; Bixby, Robert E.; Chvatal, Vasek; Cook, William; Espinoza, Daniel G.; Goycoolea, Marcos; Helsgaun, Keld.

In: Operations Research Letters, Vol. 37, No. 1, 2009, p. 11-15.

Research output: Contribution to journalJournal articleResearchpeer-review

TY - JOUR

T1 - Certification of an optimal TSP tour through 85,900 cities

AU - Applegate, David L.

AU - Bixby, Robert E.

AU - Chvatal, Vasek

AU - Cook, William

AU - Espinoza, Daniel G.

AU - Goycoolea, Marcos

AU - Helsgaun, Keld

PY - 2009

Y1 - 2009

N2 - 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

AB - 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

KW - traveling salesman problem

KW - integer programming

KW - linear programming

U2 - 10.1016/j.orl.2008.09.006

DO - 10.1016/j.orl.2008.09.006

M3 - Journal article

VL - 37

SP - 11

EP - 15

JO - Operations Research Letters

JF - Operations Research Letters

SN - 0167-6377

IS - 1

ER -

Applegate DL, Bixby RE, Chvatal V, Cook W, Espinoza DG, Goycoolea M et al. Certification of an optimal TSP tour through 85,900 cities. Operations Research Letters. 2009;37(1):11-15. https://doi.org/10.1016/j.orl.2008.09.006