We have solved twenty previously unsolved problems from the TSPLIB. One of them is the problem with 225 cities that was contrived to be hard; the sizes of the remaining nineteen range from 1,000 to 7,397 cities.
Like all the successful computer programs for solving the TSP, our
computer program follows the scheme designed by George Dantzig, Ray
Fulkerson, and Selmer Johnson in the early nineteen-fifties. The
purpose of this preliminary report is to describe *some* of our
innovations in implementing the Dantzig-Fulkerson-Johnson scheme; we
are planning to write up a more comprehensive account of our work
soon.
Paper available at:
ftp://dimacs.rutgers.edu/pub/dimacs/TechnicalReports/TechReports/1995/95-05.ps.gz
DIMACS Home Page