Study Guide  Tucker: Applied Combinatorics  §3.3 Traveling Salesperson Problem Dr. Lee Eimers Revised 11-07-07

Introduction:  This problem is one of the most famous applications of graph theory and gives us a concrete example for considering all sorts of interesting techniques.  It is representative of a larger class of problems known as combinatorial optimization problems.

1.  When you use the branch-and-bound method, you should choose the zero that results in the greatest increase in the lower bound for the "without" branch.  This will mean that it is less likely that the lower bound on the "with" branch will pass the lower bound on the "without" branch.  Every possible combination of choices occurs somewhere on the tree, so ultimately no matter which edge you choose to work with, you will eventually get to the optimum combination.

2.  "Near optimal" tours may not sound so hot, especially if it could be twice as large as the best solution.  But most times the approximate construction method will yield a much better answer than that and much more quickly than the "branch and bound" method, which for large problems may be beyond the capability of even the largest computers.