Dual ascent for branch and bound on the traveling salesman problem

Abstract

This thesis is a comparative study of several implementations of dual ascent for branch and bound on the Euclidean Traveling Salesman Problem. The work follows largely from the work of Malik and Fisher [Malik 90], where a sorted edge list was used in the implementation. Tarjan's Transmuter Graph structure for sensitivity analysis of minimum spanning trees given in [Tarjan 79], [Tarjan 82] is examined, and a dual ascent implementation using it is presented. The best dual ascent implementation found combines the strengths of the sorted edge list and the transmuter graph. All methods are compared with the subgradient ascent of Volgenant and Jonker [Volgenant 82]. The subgradient method is found empirically to be much faster than any dual ascent method, when considered in a branch and bound algorithm.