Finding the Shortest Traveling Salesman Tour
Finding the Shortest Traveling Salesman Tour
For sets of points that are not too large one can solve the traveling salesman problem—find the shortest cycle that visits all the points—by using integer linear programming (ILP), available in Mathematica via the Minimize function. Given points, introduce a variable for each possible edge, , the idea being that =1 means that one goes from to in the tour. Then create the equations that force and that each vertex has degree exactly 2, and use the objective function that sums the product of the distances between points with .
n
x
ij
1≤i<j≤n
x
ij
i
j
0≤≤1
x
ij
x
ij
Using ILP guarantees that the solutions are integers (and therefore are either 0 or 1). The optimal solution to this linear programming problem will likely be a set of disjoint cycles, as opposed to a single cycle. The total length of that set provides a lower bound on the optimal tour length. One can then add equations that destroy the cycles and run the minimizer again in the hope that, after not too many iterations of this process, the result will be a single cycle. That must then be the optimal TSP solution for the given points. For sets of up to 200 points this method works well, in that not too many iterations are needed. It is a bit slow for more than 50 points, as can be seen in the logarithmic timing chart; thus for this Demonstration the cycles for each step have been precomputed.
The points in these examples are defined by a slight perturbation of the Gaussian primes.