Bill Cook and the TSP
Bill Cook gave a talk at Waterloo about some of his work on the Traveling Salesman Problem (TSP). He has worked in the area for something like two decades. Here are some notes and highlights of his talk.
One of his main research interests is the solution of TSPs to optimality. It’s worth pointing out that many traditional applications are interested in getting cheap solutions, which many approximation algorithms will give you; so then why should we bother to solve for the cheapest solution (which is potentially much computationally harder, since TSP is NP-complete)? He gave one recent example of radiation hybrid genome sequencing where the exact optimum is needed, and his work has been used to improve clinical sequencing operations.
Recently (with some colleagues) he was able to solve the largest unsolved TSPLIB instance to optimality; it had about half a million cities. It took many computer-years of time; for this reason he stressed the importance of having a method to independently verify the optimality of the computation’s result. However, by cleverly extracting the appropriate “certificates,” the optimality of the best solution can be verified in just about 12 hours of computer time.
He also pointed out that the CPLEX “default optimality tolerance” is about 0.0001%, and that if a user were unaware of this, they could easily find an “optimal” solution to an IP which is actually non-optimal. Along these lines, he described some details of how he is working on an exact-arithmetic LP solver for use in his work. There was some mention that exact linear solving of sparse systems (e.g., Wiedermann’s method) would be useful in part of his work.
- proving lower/upper bounds on quantities of the form ±sqrt(k_i) seems to be hard, affecting exact solvability of Euclidean instances
- he’s working on a “Star TSP” with half a billion cities, and some “geometric decomposition” techniques
- duality on near-planar graphs has helped him to solve some large instances
- apparently “256-way tentative branching” is much more sweet than “strong branching.”
Filed under: algorithms, combinatorial optimization, polyhedra, talks, tsp | Leave a Comment