A dual ascent algorithm for the 1-tree relaxation of the symmetric traveling salesman problem (Q911484)

An approach to the symmetric traveling salesman problem is the 1-tree relaxation introduced by \textit{M. Held} and \textit{R. M. Karp} [Oper. Res. 18, 1138-1162 (1970; Zbl 0226.90047); Math. Program. 1, 6-25 (1971; Zbl 0232.90038)], who experimented with a dual ascent algorithm in which the primitive direction consisted of all positive and negative unit vectors, their algorithm consisted of selecting a node that was incident to more (less) than 2 edges in an optimal 1-tree, and attempting to ascend by increasing (decreasing) the dual variable for this node. This paper presents a generalization of Held and Karp's ascent algorithm, in which potential ascent directions correspond to a set of nodes that is either out of kilter high or low if the number of arcs incident on the set is either greater or less than twice the number of nodes in the set. Ascent is achieved by increasing (decreasing) all dual variables for a set of nodes out of kilter high (low) in all 1-trees that are alternate optimal at the current dual solution. The experiments on a set of both classical and randomly generated test problems up to 100 cities show that the dual ascent algorithm produced near-optimal bounds in about one-quarter of the time required by the subgradient method.