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.
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
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 ones?

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.

Some remarks


Problem a280 contains a double node, so there are essentially only 279 nodes. We have not changed the problem name, though.

References


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, North-Holland

Ju"nger, M., G. Reinelt and S. Thienel (1994), "Optimal and Provably Good Solutions for the Symmetric Traveling Salesman Problem", 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