15
\$\begingroup\$

Background

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: Segment of Drawing of pla85900 Tour

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!)

Concorde is available for download as source code or an executable. By default, it uses the built-in linear program (LP) solver QSopt, but it can also use better LP solvers like CPLEX.

The challenge

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.

Scoring

The fewer points in the instance the better. Ties will be broken by the file size of the instance (see below).

Standardization

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

Baseline

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:

no-cities illustration of rl1889.tsp

\$\endgroup\$
15
+25
\$\begingroup\$

88 Cities, 341 seconds runtime on NEOS

In a recent paper we constructed a family of hard to solve euclidean TSP instances. You can download the instances from this family as well as code for generating them here:

http://www.or.uni-bonn.de/%7Ehougardy/HardTSPInstances.html

The 88 city instance from this family takes Concorde on the NEOS server more than 5 minutes. The 178-city instance from this family takes already more than a day to solve.

\$\endgroup\$
  • 1
    \$\begingroup\$ This is amazing!! \$\endgroup\$ – A. Rex Feb 8 at 0:35
  • \$\begingroup\$ Very nice paper! Amazing outcome. You totally deserve the win on this! \$\endgroup\$ – agtoever Feb 8 at 20:09
5
\$\begingroup\$

Python 3, 911 cities, 1418 seconds of run time on NEOS

The following Python 3.x script generates the coordinates of 911 cities. It took NEOS 1418 seconds to calculate the shortest path of 47739.

Here is A picture of thee shortest path (thanks to A. Rex): shortest path between 911 cities

The code/algorithm is based on the Feigenbaum bifurcation, which I used to generate a series of values, which I used as a basis for generating the coordinates of the cities. I experimented with the parameters until I found a number of cities under 1000 that took NEOS a surprising amount of time (well above the required 5 minutes).

x = 0.579
coords = []
for _ in range(1301):
    if int(3001*x) not in coords:
        coords.append(int(3001*x))
    x = 3.8*x*(1-x)
coords = list(zip(coords, coords[::-1]))
print(len(coords))
for coord in coords:
    print(f"{coord[0]} {coord[1]}")

PS: I have a script running in search for a lower number of cities that also take >5 minutes on NEOS. I'll post them in this answer if I find any.

PS: Damn! Running this script with l parameter 1811 instead of 1301 results in 1156 cities with a running time on NEOS of just over 4 hours, which is a lot more than other cases with similar parameters...

\$\endgroup\$
  • \$\begingroup\$ Here's a picture of your 911-city tour if you want to edit it into your post: i.imgur.com/G1ZPX0k.png \$\endgroup\$ – A. Rex Feb 9 at 15:30
  • \$\begingroup\$ @A.Rex thanks. Added it. \$\endgroup\$ – agtoever Feb 9 at 16:41

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.