How do we know a TSP tour is optimal?
Applet Demonstrating the Cutting-Plane Method
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.
| |
How do we know a TSP tour is optimal? Applet Demonstrating the Cutting-Plane Method |