Document Open Access Logo

A k-Opt Based Constraint for the TSP

Authors Nicolas Isoart, Jean-Charles Régin

PDF

File

Thumbnail PDF
PDF
LIPIcs.CP.2021.30.pdf
  • Filesize: 0.71 MB
  • 16 pages

Document Identifiers

Subject Classification

ACM Subject Classification
  • Theory of computation → Constraint and logic programming
Keywords
  • TSP
  • k-opt
  • 1-tree
  • Constraint

Metrics

Abstract

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.

Cite As Get BibTex

Nicolas Isoart and Jean-Charles Régin. A k-Opt Based Constraint for the TSP. In 27th International Conference on Principles and Practice of Constraint Programming (CP 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 210, pp. 30:1-30:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021) https://doi.org/10.4230/LIPIcs.CP.2021.30

Author Details

Nicolas Isoart
  • Université Côte d'Azur, Nice, France
Jean-Charles Régin
  • Université Côte d'Azur, Nice, France

Funding

This work has been supported by the 3IA Côte d’Azur with the reference number ANR-19-P3IA-0002.

References

  1. David L Applegate, Robert E Bixby, Vasek Chvatal, and William J Cook. The traveling salesman problem: a computational study. Princeton university press, 2006. Google Scholar
  2. Pascal Benchimol, Willem-Jan Van Hoeve, Jean-Charles Régin, Louis-Martin Rousseau, and Michel Rueher. Improved filtering for weighted circuit constraints. Constraints, 17(3):205-233, 2012. URL: https://hal.archives-ouvertes.fr/hal-01344070.
  3. Jon Jouis Bentley. Fast algorithms for geometric traveling salesman problems. ORSA Journal on computing, 4(4):387-411, 1992. Google Scholar
  4. Václav Chvátal. Edmonds polytopes and weakly hamiltonian graphs. Math. Program., 5(1):29-40, 1973. URL: https://doi.org/10.1007/BF01580109.
  5. George Dantzig, Ray Fulkerson, and Selmer Johnson. Solution of a large-scale traveling-salesman problem. Journal of the operations research society of America, 2(4):393-410, 1954. Google Scholar
  6. Jack Edmonds. Paths, Trees, and Flowers. Canadian Journal of Mathematics, 17:449–467, 1965. URL: https://doi.org/10.4153/CJM-1965-045-4.
  7. Jean-Guillaume Fages, Xavier Lorca, and Louis-Martin Rousseau. The salesman and the tree: the importance of search in CP. Constraints, 21(2):145-162, 2016. Google Scholar
  8. Martin Grötschel and Manfred Padberg. On the symmetric travelling salesman problem i: Inequalities. Mathematical Programming, 16:265-280, December 1979. URL: https://doi.org/10.1007/BF01582116.
  9. Robert Haralick and Gordon Elliott. Increasing Tree Search Efficiency for Constraint Satisfaction Problems. Artificial Intelligence, 14:263-313, January 1979. Google Scholar
  10. Michael Held and Richard M. Karp. The traveling-salesman problem and minimum spanning trees. Operations Research, 18(6):1138-1162, 1970. Google Scholar
  11. Michael Held and Richard M. Karp. The traveling-salesman problem and minimum spanning trees: Part ii. Mathematical Programming, 1(1):6-25, 1971. Google Scholar
  12. Keld Helsgaun. An effective implementation of the lin–kernighan traveling salesman heuristic. European Journal of Operational Research, 126(1):106-130, 2000. URL: https://doi.org/10.1016/S0377-2217(99)00284-2.
  13. Nicolas Isoart and Jean-Charles Régin. Integration of structural constraints into tsp models. In Thomas Schiex and Simon de Givry, editors, Principles and Practice of Constraint Programming, pages 284-299, Cham, 2019. Springer International Publishing. Google Scholar
  14. Nicolas Isoart and Jean-Charles Régin. Adaptive CP-Based Lagrangian Relaxation for TSP Solving. In Emmanuel Hebrard and Nysret Musliu, editors, Integration of Constraint Programming, Artificial Intelligence, and Operations Research, pages 300-316, Cham, 2020. Springer International Publishing. Google Scholar
  15. Christophe Lecoutre, Lakhdar Saïs, Sébastien Tabary, and Vincent Vidal. Reasoning from last conflict(s) in constraint programming. Artificial Intelligence, 173(18):1592-1614, 2009. Google Scholar
  16. Adam N. Letchford and Andrea Lodi. Polynomial-Time Separation of Simple Comb Inequalities. In William J. Cook and Andreas S. Schulz, editors, Integer Programming and Combinatorial Optimization, pages 93-108, Berlin, Heidelberg, 2002. Springer Berlin Heidelberg. Google Scholar
  17. S. Lin and B. Kernighan. An effective heuristic algorithm for the traveling-salesman problem. Oper. Res., 21:498-516, 1973. Google Scholar
  18. Shen Lin. Computer solutions of the traveling salesman problem. Bell System Technical Journal, 44:2245-2269, 1965. Google Scholar
  19. Ilhan Or. Traveling salesman type combinatorial problems and their relation to the logistics of regional blood banking, 1977. Google Scholar
  20. Gerhard Reinelt. TSPLIB - A Traveling Salesman Problem Library. ORSA Journal on Computing, 3(4):376-384, 1991. Google Scholar
  21. Robert E. Tarjan. Data Structures and Network Algorithms. CBMS-NSF Regional Conference Series in Applied Mathematics, 1983. Google Scholar
Any Issues?
X

Feedback on the Current Page

CAPTCHA

Thanks for your feedback!

Feedback submitted to Dagstuhl Publishing

Could not send message

Please try again later or send an E-mail
© 2023-2025 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact