10235

# 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. Walk through homework problems one step at a time, with hints to help along the way. Unlimited random practice problems and answers with built-in Step-by-step solutions. Practice online or make a printable study sheet. Knowledge-based programming for everyone.