The traveling salesman problem asks for an optimal tour through a specified set of cities. To solve a particular instance of the problem we must find a shortest tour and verify that no better tour exists. ln this section we describe some of the techniques employed in the Concorde code for the TSP, focusing on the difficult verification task.

       

Progress in solving TSPs

How do we know a TSP tour is optimal?

The Cutting-Plane Method

Applet Demonstrating the Cutting-Plane Method

TSP Lectures by Vasek Chvatal and William Cook

TSP Research Papers