Fictitious upper bounds in an algorithm for the symmetric traveling salesman problem

The performance of a branch and bound algorithm depends on the quality of the upper bounds. For a depth first search strategy this dependence is larger than for a breadth first strategy. If no good upper bounding heuristic is available, one may decide to use fictitious upper bounds. We discuss the use of three types of these bounds in an algorithm for the symmetric traveling salesman problem (TSP). Computational results illustrate the discussion for problems with up to 200 cities and of different problem types.