×

A dual ascent algorithm for the 1-tree relaxation of the symmetric traveling salesman problem. (English) Zbl 0696.90078

An approach to the symmetric traveling salesman problem is the 1-tree relaxation introduced by M. Held and 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.
Reviewer: Z.Liu

MSC:

90C35 Programming involving graphs or networks
65K05 Numerical mathematical programming methods
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] N. Christofides, “Worst-case analysis of a new heuristic for the traveling salesman problem”, Report 388, Graduate School of Industrial Administration, Carnegie Mellon University, Pittsburgh.; N. Christofides, “Worst-case analysis of a new heuristic for the traveling salesman problem”, Report 388, Graduate School of Industrial Administration, Carnegie Mellon University, Pittsburgh.
[2] Dantzig, G. B.; Fulkerson, D. R.; Johnson, S. M., Solution of a large scale traveling salesman problem, Oper. Res., 2, 393-410 (1954) · Zbl 1414.90372
[3] Erlenkotter, D., A dual-based procedure for uncapacitated facility location, Oper. Res., 26, 992-1009 (1978) · Zbl 0422.90053
[4] Fisher, M. L., The Lagrangian relaxation method for solving integer programming problems, Management Sci., 27, 1-18 (1981) · Zbl 0466.90054
[5] Fisher, M. L.; Jaikumar, R.; Van Wassenhove, L., A multiplier adjustment method for the generalized assignment problem, Management Sci., 32, 1095-1103 (1986) · Zbl 0626.90036
[6] Held, H.; Karp, R. M., The traveling salesman problem and minimum spanning trees, Oper. Res., 18, 1138-1162 (1970) · Zbl 0226.90047
[7] Held, H.; Karp, R. M., The traveling salesman problem and minimum spanning trees: Part II, Math. Programming, 1, 6-25 (1971) · Zbl 0232.90038
[8] Held, H.; Karp, R. M., A dynamic programming approach to sequencing problems, J. SIAM, 10, 196-210 (1962) · Zbl 0106.14103
[9] Held, M.; Wolfe, P.; Crowder, H. P., Validation of subgradient optimization, Math. Programming, 6, 62-88 (1974) · Zbl 0284.90057
[10] O.A. Holland, Personal communication.; O.A. Holland, Personal communication.
[11] Jonker, R., Traveling salesman problem and assignment algorithms: Design and implementation, (PhD Thesis (1986), University of Amsterdam: University of Amsterdam Amsterdam)
[12] Karg, L. L.; Thompson, G. L., A heuristic approach to solving traveling salesman problems, Management Sci., 10, 225-248 (1964)
[13] Lemarechal, C., An extension of Davidson methods to non differentiable problems, Math. Programming Stud., 3, 95-109 (1975)
[14] M.G. Pilcher and R.L. Rardin, “A random cut generator for symmetric traveling salesman problems with known optimal solutions”, CC-87-4, Computational Combinatorics, IIES, Purdue University.; M.G. Pilcher and R.L. Rardin, “A random cut generator for symmetric traveling salesman problems with known optimal solutions”, CC-87-4, Computational Combinatorics, IIES, Purdue University.
[15] Tarjan, R. E., Applications of path compression on balanced trees, JACM, 26, 4, 690-715 (1979) · Zbl 0413.68063
[16] Tarjan, R. E., Sensitivity analysis of minimum spanning trees and shortest path trees, Information Processing Lett., 14, 30-33 (1982)
[17] Wolfe, P., A method of conjugate subgradients for minimizing nondifferentiable functions, Math. Programming Stud., 3, 145-173 (1975)
[18] Wong, R. T., A dual ascent approach for Steiner tree problems on a directed graph, Math. Programming, 28, 271-287 (1984) · Zbl 0532.90092
[19] Krolak, P.; Felts, W.; Marble, G., A man-machine approach toward solving the traveling salesman problem, CASM, 14, 327-334 (1971) · Zbl 0217.27302
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.