2026-07-26T00:38:40Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:15321 2024-03-06T10:55:07Z ddc:004 open_access

A k-Opt Based Constraint for the TSP Isoart, Nicolas Régin, Jean-Charles TSP k-opt 1-tree Constraint The LKH algorithm based on k-opt is an extremely efficient algorithm solving the TSP. Given a non-optimal tour in a graph, the idea of k-opt is to iteratively swap k edges of this tour in order to find a shorter tour. However, the optimality of a tour cannot be proved with this method. In that case, exact solving methods such as CP can be used. The CP model is based on a graph variable with mandatory and optional edges. Through branch-and-bound and filtering algorithms, the set of mandatory edges will be modified. In this paper, we introduce a new constraint to the CP model named mandatory Hamiltonian path constraint searching for k-opt in the mandatory Hamiltonian paths. Experiments have shown that the mandatory Hamiltonian path constraint allows us to gain on average a factor of 3 on the solving time. In addition, we have been able to solve some instances that remain unsolved with the state of the art CP solver with a 1 week time out. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Nicolas Isoart and Jean-Charles Régin 2021 Is Part Of LIPIcs, Volume 210, 27th International Conference on Principles and Practice of Constraint Programming (CP 2021) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.CP.2021.30 urn:nbn:de:0030-drops-153212 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CP.2021.30 eng https://creativecommons.org/licenses/by/4.0/legalcode