Certification of an optimal TSP tour through 85,900 cities

被引：96

作者：

Applegate, David L.

Bixby, Robert E. ^{[2
]}

Chvatal, Vasek ^{[3
]}

Cook, William ^{[1
]}

Espinoza, Daniel G. ^{[4
]}

Goycoolea, Marcos ^{[5
]}

Helsgaun, Keld ^{[6
]}

机构：

[1] Georgia Tech, Sch Ind & Syst Engn, Atlanta, GA 30332 USA

[2] Rice Univ, Grad Sch Management, Houston, TX 77251 USA

[3] Concordia Univ, Dept Comp Sci & Software Engn, Montreal, PQ, Canada

[4] Univ Chile, Dept Ingn Ind, Santiago, Chile

[5] Univ Adolfo Ibanez, Sch Business, Recreo, Chile

[6] Roskilde Univ, Dept Comp Sci, Roskilde, Denmark

来源：

OPERATIONS RESEARCH LETTERS | 2009年 / 37卷 / 01期

关键词：

Traveling salesman problem; Integer programming; Linear programming; INEQUALITIES; ALGORITHM;

D O I：

10.1016/j.orl.2008.09.006

中图分类号：

C93 [管理学]; O22 [运筹学];

学科分类号：

070105 ; 12 ; 1201 ; 1202 ; 120202 ;

摘要：

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. (C) 2008 Elsevier B.V. All rights reserved.

引用

页码：11 / 15

页数：5

共 20 条

[1]

[Anonymous], 1971, Math Program, DOI DOI 10.1007/BF01584070

[2] Implementing the Dantzig-Fulkerson-Johnson algorithm for large traveling salesman problems [J].