TSPLIB: Questions and answers
Q: I found a better solution than the one claimed to be optimal in TSPLIB,
is this possible?
A: This never occured so far. In
all cases when someone believed to have found a better solution, it
was not taken into account that it is exactly specified how distances
for TSPLIB problems have to computed. Typical errors are
Note, however, that due to round-off errors distance evaluations may slightly differ on different machines.
distances for geometric problem instances as floating-point numbers,
false computation of geographic distances,
use of display coordinates for distance computations.
Q: I get wrong distances for problems of type GEO.
A: In a previous release there was a typing error in the distance
specification for these problems. The formulae for computing latitude[i]
and longitude[i] should read
latitude[i] = PI * (deg + 5.0 * min / 3.0 ) / 180.0;
longitude[i] = PI * (deg + 5.0 * min / 3.0 ) / 180.0;
Q: What does the function nint() do?
A: The function "int nint (double x)"
converts x into int format rounding to the nearest
int value, except halfway cases are rounded to the int value
larger in magnitude. This corresponds to the Fortran generic
intrinsic function nint.
Q: Are contributions still welcome?
A: Basically yes, but, in view of the many problem instances that are
already available, new instances should either be real challenge
problems or be of general interest.
Q: Is an optimal tour available for every solved problem instance?
A: No. We have included several optimal tours for testing purposes. It is
not intended to provide all optimal tours. It should still be a
challenge to find one.
Q: Are there optimal solutions available for instances other than symmetric
A: So far, no other optimal solutions have been made available.
Q: Which format has been used to store the data?
A: All data has been compressed with the command "gzip" and has to be
read using "gzip -d". Please contact your system administrator
if this command is not available.
Problem a280 contains a double node, so there are essentially only 279 nodes.
We have not changed the problem name, though.
Applegate, D., Bixby, R., Chvatal, V. and W. Cook (1994),
"Finding cuts in the TSP (A preliminary report)",
Research Report, Rice University
Ju"nger, M., G. Reinelt and G. Rinaldi (1996),
"The Traveling Salesman Problem", in:
M. Ball, T. Magnanti, C. L. Monma and G.L. Nemhauser (eds.),
Handbooks in Operations Research and Management Sciences: Networks,
Ju"nger, M., G. Reinelt and S. Thienel (1994),
"Optimal and Provably Good Solutions for the Symmetric Traveling
Zeitschrift fu"r Operations Research (40), 183-217
Padberg, M.W. and G. Rinaldi (1987),
"Optimization of a 532 City Symmetric Traveling Salesman Problem by
Branch and Cut",
Operations Research Letters (6), 1-7
Padberg, M.W. and G. Rinaldi (1991),
"A Branch and Cut Algorithm for the Resolution of Large-scale Symmetric
Traveling Salesman Problems"
SIAM Review (33), 60-100}
Last change: December 05, 1996