**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

- evaluation of distances for geometric problem instances as floating-point numbers,
- false computation of geographic distances,
- use of display coordinates for distance computations.

**A**: No, for every problem either the value of a provably optimal
solution or an interval given by the best known lower and upper bound is
listed. The optimality of solutions has been proven by branch-and-cut or
branch-and-bound algorithms.

**A**: There has been some confusion of how to compute the distances.
I use the following code.

For converting coordinate input to longitude and latitude in radian:

PI = 3.141592;

deg = (int) x[i];

min = x[i]- deg;

rad = PI * (deg + 5.0 * min/ 3.0) / 180.0;

For computing the geographical distance:

RRR = 6378.388;

q1 = cos( longitude[i] - longitude[j] );

q2 = cos( latitude[i] - latitude[j] );

q3 = cos( latitude[i] + latitude[j] );

dij = (int) ( RRR * acos( 0.5*((1.0+q1)*q2 - (1.0-q1)*q3) ) +
1.0);

**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. But, rounding like "(int) (x+0.5)" should give
the same results for TSPLIB problems.

Actually, it is better to use just
"int" as in the previous answer.

**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.

**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.

**A**: So far, no other optimal solutions have been made available.

**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.

Jü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

Jünger, M., G. Reinelt and G. Rinaldi (1997), "The Traveling Salesman Problem", in: M. Dell' Amico, F. Maffioli, S. Martello (eds.), Annotated Bibliographies in Combinatorial Optimization, 199-221, Wiley

Jü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: November 9, 2000