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

Publikation: Bidrag til tidsskriftTidsskriftartikelForskningpeer review

Resumé

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
OriginalsprogEngelsk
TidsskriftOperations Research Letters
Vol/bind37
Udgave nummer1
Sider (fra-til)11-15
Antal sider6
ISSN0167-6377
DOI
StatusUdgivet - 2009

Citer dette

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. I: Operations Research Letters. 2009 ; Bind 37, Nr. 1. s. 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, bind 37, nr. 1, s. 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.

I: Operations Research Letters, Bind 37, Nr. 1, 2009, s. 11-15.

Publikation: Bidrag til tidsskriftTidsskriftartikelForskningpeer 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