Estimating the Held-Karp lower bound for the geometric TSP. (English) Zbl 0948.90034

Summary: The Held-Karp lower bound (HK) provides a very good problem-specific estimate of optimal tour length for the travelling salesman problem (TS). This measure, which is relatively quick and easy to compute, has enormous practical value when evaluating the quality of near optimal solutions for large problems where the true optima are not known. Although HK can be evaluated exavtly by Linear Programming techniques, code for doing this efficiently for problems larger than a few hundred cities is not readily available or easy to produce. In addition Linear Programming implementations (even efficient ones) do not scale well and rapidly become impractical for problems with many thousands of cities. In this study we concentrate on the iterative estimation approach proposed by Held and Karp in their original papers. Our paper provides implementation details for two iterative schemes which both use the subgraph speed-up technique. We begin by surveying the important theoretical issues which underpin the original iterative approach of Held and Karp (now known as subgradient optimisation). We then present some detailed practical guidelines for the evaluation of HK for large geometric TSP problems, and also provide some empirical evidence demonstrating the robustness of the iterative schemes we have been used. Finally our estimation of the Goemans and Bertsimas constant provides an independent confirmation of the value published recently by Johnson, McGeoch and Rothberg and simultaneously supports the claim that our approach does indeed produce reliable results.


90B20 Traffic problems in operations research
90C52 Methods of reduced gradient type


Full Text: DOI


[1] Applegate, D.; Bixby, R.; Chvátal, V.; Cook, W., Finding cuts in the TSP (A preliminary report), ()
[2] Balas, E.; Toth, P., Branch and bound methods, () · Zbl 0568.90068
[3] Beardwood, J.; Halton, J.H.; Hammersley, J.M., The shortest path through many points, (), 299-327 · Zbl 0118.35601
[4] Bently, J.L., Multidimensional binary search trees used for associative search, Communications of the ACM, 18, 309-517, (1975)
[5] Christophides, N., The traveling salesman problem, ()
[6] Goemans, M.X.; Bertsimas, D.J., Probabilistic analysis of the held and karp lower bound for the Euclidean traveling salesman problem, Mathematics of operations research, 16, 1, 72-89, (1991) · Zbl 0733.90072
[7] Helbig-Hansen, K.H.; Krarup, J., Improvements of the held-karp algorithm for the symmetric traveling salesman problem, Mathematical programming, 7, 87-96, (1974) · Zbl 0285.90055
[8] Held, M.; Karp, R.M., The traveling salesman problem and minimum spanning trees, Operations research, 18, 1138-1162, (1970) · Zbl 0226.90047
[9] Held, M.; Karp, R.M., The traveling salesman problem and minimum spanning trees, part II, Mathematical programming, 1, 6-25, (1971) · Zbl 0232.90038
[10] Held, M.; Wolfe, P.; Crowder, H.P., Validation of subgradient optimization, Mathematical programming, 6, 62-88, (1974) · Zbl 0284.90057
[11] Horowitz, E.; Sahni, S., Fundamentals of computer algorithms, (1978), Pitman · Zbl 0442.68022
[12] Johnson, D.S., ()
[13] Johnson, D.S., Local optimization and the traveling salesman problem, () · Zbl 0766.90079
[14] Johnson, D.S.; Mcgeoch, L.A., The traveling salesman problem: A case study in local optimization, (), To appear in · Zbl 0845.90123
[15] Johnson, D.S., 1995b. Personal communication.
[16] Johnson, D.S.; McGeoch, L.A.; Rothberg, E.E., Asymptotic experimental analysis for the held-karp traveling salesman bound, () · Zbl 0845.90123
[17] Polyak, B.T.; Polyak, B.T., A general method of solving extremal problems, Soviet mathematics doklady, Doklady akademii nauk SSSR, 174, 593-597, (1967), Translation of · Zbl 0177.15102
[18] Polyak, B.T.; Polyak, B.T., Minimization of unsmooth functionals, Computational mathematics and mathematical physics, Žurnal vyčislitel’noǐ matematiki i matematičesko fiziki, 9, 509-521, (1969), Translation of · Zbl 0229.65056
[19] Reinelt, G., The traveling salesman: computational solutions for TSP applications, ()
[20] Reinelt, G., A library of TSP problems from: E-mail: elib@ZIB-Berlin.de. telnet: elib.zib-Berlin.de, (1995)
[21] Shamos, M.I.; Hoey, D., Closest point problems, (), 151-162
[22] Shmoys, D.B.; Williamson, D.P., Analyzing the held-karp TSP bound: A monotonicity property with application, Information processing letters, 35, 281-285, (1990) · Zbl 0698.68050
[23] Stein, D., Scheduling dial-a-ride transportation systems: an asymptotic approach, ()
[24] Valenzuela, C.L.; Jones, A.J., Evolutionary divide and conquer(I): a novel genetic approach to the TSP, Evolutionary computation, 1, 4, 313-333, (1994)
[25] Valenzuela, C.L.; Jones, A.J., A parallel implementation of evolutionary divide and conquer for the TSP, (), 499-504
[26] Valenzuela, C.L., Evolutionary divide and conquer: a novel genetic approach to the TSP, (1995), Imperial College, University of London, Unpublished Ph.D. thesis
[27] Volgenant, T.; Jonker, R., A branch and bound algorithm for the symmetric traveling salesman problem based on the 1-tree relaxation, European journal of operational research, 9, 83-89, (1982) · Zbl 0471.90088
[28] Wichmann, B.A.; Hill, D., A pseudo-random number generator, National physical laboratory U.K. report DITC 6-82, (1982)
[29] Wolsey, L., Heuristic analysis, linear programming and branch and bound, Mathematical programming study, 13, 121-134, (1980) · Zbl 0442.90061
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. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.