ESTIMATING THE HELD-KARP LOWER-BOUND FOR THE GEOMETRIC TSP

The Held-Karp lower bound (HK) provides a very good problem-specific e stimate of optimal tour length for the travelling salesman problem (TS P). This measure, which is relatively quick and easy to compute, has e normous practical value when evaluating the quality of near optimal so lutions for large problems where the true optima are not known. Althou gh HK can be evaluated exactly by Linear Programming techniques, code for doing this efficiently for problems larger than a few hundred citi es is not readily available or easy to produce. In addition Linear Pro gramming implementations (even efficient ones) do not scale well and r apidly become impractical for problems with many thousand of cities. I n this study we concentrate on the iterative estimation approach propo sed by Held and Karp in their original papers. Our paper provides impl ementation details for two iterative schemes which both use the subgra ph speed-up technique. We begin by surveying the important theoretical issues which underpin the original iterative approach of Held and Kar p (now known as subgradient optimisation). We then present some detail ed practical guidelines for the evaluation of HK for large geometric T SP problems, and also provide some empirical evidence demonstrating th e robustness of the iterative schemes we have used. Finally our estima tion of the Goemans and Bertsimas constant provides and independent co nfirmation of the value published recently by Johnson, McGeoch and Rot hberg and simultaneously supports the claim that our approach does ind eed produce reliable results. (C) 1997 Elsevier Science B.V.