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

doi:10.1016/j.orl.2008.09.006

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

Programming, Logic and Intelligent Systems

Research output: Contribution to journal › Journal article › Research › peer-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 language	English
Journal	Operations Research Letters
Volume	37
Issue number	1
Pages (from-to)	11-15
Number of pages	6
ISSN	0167-6377
DOIs	https://doi.org/10.1016/j.orl.2008.09.006
Publication status	Published - 2009

Keywords

traveling salesman problem
integer programming
linear programming

Link to document

10.1016/j.orl.2008.09.006

Cite this

@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",

}

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

SN - 0167-6377

VL - 37

SP - 11

EP - 15

JO - Operations Research Letters

JF - Operations Research Letters

IS - 1

ER -