Estimating the Held-Karp lower bound for the geometric TSP

Mumford, Christine Lesley ORCID: https://orcid.org/0000-0002-4514-0272 and Jones, Antonia J. 1997. Estimating the Held-Karp lower bound for the geometric TSP. European Journal of Operational Research 102 (1) , pp. 157-175. 10.1016/S0377-2217(96)00214-7

Preview

Text Download (200kB) | Preview

Abstract

The Held-Karp lower bound (HK) provides a very good problem-specific estimate of optimal tour length for the travelling salesman problem (TSP). 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 exactly 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.

Item Type:	Article
Date Type:	Publication
Status:	Published
Schools:	Computer Science & Informatics
Subjects:	Q Science > QA Mathematics Q Science > QA Mathematics > QA75 Electronic computers. Computer science Q Science > QA Mathematics > QA76 Computer software
Uncontrolled Keywords:	Travelling salesman; Held-Karplowerbound; Minimum 1-tree; Lagrangian relaxation; Subgradient optimization
Publisher:	Elsevier
ISSN:	0377-2217
Last Modified:	13 May 2023 09:40
URI:	https://orca.cardiff.ac.uk/id/eprint/31865

Actions (repository staff only)

Edit Item