zbMATH — the first resource for mathematics

Improving the Held and Karp approach with constraint programming. (English) Zbl 1285.68149
Lodi, Andrea (ed.) et al., Integration of AI and OR techniques in constraint programming for combinatorial optimization problems. 7th international conference, CPAIOR 2010, Bologna, Italy, June 14–18, 2010. Proceedings. Berlin: Springer (ISBN 978-3-642-13519-4/pbk). Lecture Notes in Computer Science 6140, 40-44 (2010).
Summary: Held and Karp have proposed, in the early 1970s, a relaxation for the Traveling Salesman Problem (TSP) as well as a branch-and-bound procedure that can solve small to modest-size instances to optimality. It has been shown that the Held-Karp relaxation produces very tight bounds in practice, and this relaxation is therefore applied in TSP solvers such as Concorde [D. L. Applegate et al., The traveling salesman problem. A computational study. Princeton, NJ: Princeton University Press (2006; Zbl 1130.90036)]. In this short paper we show that the Held-Karp approach can benefit from well-known techniques in Constraint Programming (CP) such as domain filtering and constraint propagation. Namely, we show that filtering algorithms developed for the weighted spanning tree constraint [G. Dooms and I. Katriel, Lect. Notes Comput. Sci. 4510, 59–70 (2007; Zbl 1214.90121); J.-C. Régin, Lect. Notes Comput. Sci. 5015, 233–247 (2008; Zbl 1142.68523)] can be adapted to the context of the Held and Karp procedure. In addition to the adaptation of existing algorithms, we introduce a special-purpose filtering algorithm based on the underlying mechanisms used in Prim’s algorithm [R. C. Prim, “Shortest connection networks and some generalizations”, Bell Syst. Tech. J. 36, 1389–1401 (1957; doi:10.1002/j.1538-7305.1957.tb01515.x)]. Finally, we explored two different branching schemes to close the integrality gap. Our initial experimental results indicate that the addition of the CP techniques to the Held-Karp method can be very effective.
The paper is organized as follows: section 2 describes the Held-Karp approach while section 3 gives some insights on the Constraint Programming techniques and branching scheme used. In section 4 we demonstrate, through preliminary experiments, the impact of using CP in combination with Held and Karp based branch-and-bound on small to modest-size instances from the TSPlib.
For the entire collection see [Zbl 1189.68014].

68T20 Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.)
90C27 Combinatorial optimization
Full Text: DOI