8769

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

### DETAILS

The snapshots show the three iterations required to find the optimal solution in the case of 60 points; that requires only three seconds.
The equations used to set the degrees are: for each . The inequality used to break a cycle is: . The objective function that is minimized is: , where is the point.
For more details, see Chapter 13 of S. Wagon, Mathematica in Action, 3rd ed., New York, Springer, 2010.

### PERMANENT CITATION

Contributed by: Stan Wagon (Macalester College)
 Share: Embed Interactive Demonstration New! Just copy and paste this snippet of JavaScript code into your website or blog to put the live Demonstration on your site. More details » Download Demonstration as CDF » Download Author Code »(preview ») Files require Wolfram CDF Player or Mathematica.

#### Related Topics

 RELATED RESOURCES
 The #1 tool for creating Demonstrations and anything technical. Explore anything with the first computational knowledge engine. The web's most extensive mathematics resource. An app for every course—right in the palm of your hand. Read our views on math,science, and technology. The format that makes Demonstrations (and any information) easy to share and interact with. Programs & resources for educators, schools & students. Join the initiative for modernizing math education.
 © 2013 Wolfram Demonstrations Project & Contributors  |  Terms of Use  |  Privacy Policy  |  RSS
 Note: To run this Demonstration you need Mathematica 7+ or the free Mathematica Player 7EX Download or upgrade to Mathematica Player 7EX I already have Mathematica Player or Mathematica 7+