Efficient Branch and Bound Code for Solving Large Scale Travelling Salesman Problems to Optimality
Kizhanatham Srikanth, Bezalel Gavish · UR Research (University of Rochester) · 1983
In this paper, we develop a solution method for the symmetric TSP that is a major modification of a solution procedure developed by Held and Karp [1970,1971). A Lagrangean relaxation is performed on the original problem. The solution to the relaxed problem is a minimal l-tree. Sensitivity analysis techniques for spanning trees are used to eliminate most of the arcs in the original problem, as well as to identify arcs which must be part of the optimal solution to the TSP. When sufficient levels of graph sparsity have been reached, an algorithm designed for use on sparse graphs is used to compute the minimal l-trees, thus reducing the computing time expended. The graph sparsity is also exploited throughout the final branch and bound procedure by using vertex/arc connectivity concepts to assist in fathoming portions of the branch and bound tree.