The traveling salesman problem (TSP) asks for the shortest circuit that visits a given collection of cities. For the purposes of this question, the cities will be points in the plane and the distances between them will be the usual Euclidean distances (rounded to the nearest integer). The circuit must be "round-trip", meaning it must return to the starting city.
The Concorde TSP solver can solve instances of the Euclidean traveling salesman problem, exactly and much faster than one would expect. For example, Concorde was able to solve an 85,900-point instance exactly, parts of which look like this:
However, some TSP instances take too long, even for Concorde. For example, no one has been able to solve this 100,000-point instance based on the Mona Lisa. (There is a $1,000 prize offered if you can solve it!)
What is the smallest TSP instance you can generate that takes Concorde more than five minutes to solve?
You can write a program to output the instance, or use any other method you would like.
The fewer points in the instance the better. Ties will be broken by the file size of the instance (see below).
Different computers run faster or slower, so we will use the NEOS Server for Concorde as the standard of measurement for runtime. You can submit a list of points in the following simple 2-d coordinate form:
#cities x_0 y_0 x_1 y_1 . . . x_n-1 y_n-1
The settings that should be used on NEOS are "Concorde data(xy-list file, L2 norm)", "Algorithm: Concorde(QSopt)", and "Random seed: fixed".
The 1,889-point instance
rl1889.tsp from TSPLIB takes "Total Running Time: 871.18 (seconds)", which is more than five minutes. It looks like this: