{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,7,28]],"date-time":"2026-07-28T01:29:46Z","timestamp":1785202186390,"version":"3.55.0"},"reference-count":48,"publisher":"Oxford University Press (OUP)","issue":"2","license":[{"start":{"date-parts":[[2026,1,27]],"date-time":"2026-01-27T00:00:00Z","timestamp":1769472000000},"content-version":"vor","delay-in-days":1,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2026,1,26]]},"abstract":"<jats:title>Abstract<\/jats:title>\n                  <jats:p>The Travelling Salesperson Problem (TSP) is a very well-known problem in computer science. Many real-world instances belong to the class of Euclidean TSP, in which the nodes to be visited lie on the Euclidean plane, and additional information is available with respect to the generic TSP, i.e. the coordinates of the nodes to be visited are known. In previous publications, we showed that the additional available information can be exploited to speed up the search, both in Constraint Logic Programming (CLP) and in Answer Set Programming (ASP). Constraint ASP (CASP) is a framework that joins CLP and ASP, and it aims at combining the features of both languages. In this article, we address the (Euclidean) TSP in CASP, and more specifically in the clingo$[DL]$ language and solver. We propose new encodings for the TSP in clingo$[DL]$; the new encodings are applicable to the general TSP (also to instances that are not Euclidean) and show a speedup of several orders of magnitude with respect to previous encodings. A further speedup can be obtained in Euclidean instances by exploiting geometric reasoning.<\/jats:p>","DOI":"10.1093\/logcom\/exaf072","type":"journal-article","created":{"date-parts":[[2025,11,13]],"date-time":"2025-11-13T13:00:34Z","timestamp":1763038834000},"source":"Crossref","is-referenced-by-count":1,"title":["New encodings of the (Euclidean) travelling salesperson problem in constraint answer set programming on difference logic"],"prefix":"10.1093","volume":"36","author":[{"given":"Alessandro","family":"Bertagnon","sequence":"first","affiliation":[{"name":"Department of Environmental and Prevention Sciences, University of Ferrara , C.so Ercole I D\u2019Este, 32, Ferrara ,","place":["Italy"]}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Marco","family":"Gavanelli","sequence":"additional","affiliation":[{"name":"Department of Engineering, University of Ferrara , Via Saragat 1, Ferrara ,","place":["Italy"]}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"286","published-online":{"date-parts":[[2026,1,26]]},"reference":[{"key":"2026012711402475900_ref1","doi-asserted-by":"crossref","first-page":"241","DOI":"10.1007\/978-3-030-20528-7_18","article-title":"Evaluation of disjunctive programs in wasp","volume-title":"Logic Programming and Nonmonotonic Reasoning","author":"Alviano","year":"2019"},{"key":"2026012711402475900_ref2","doi-asserted-by":"crossref","first-page":"261","DOI":"10.1007\/3-540-45586-8_7","article-title":"TSP cuts which do not conform to the template paradigm","volume-title":"Computational Combinatorial Optimization, Optimal or Provably Near-Optimal Solutions [Based on a Spring School, Schlo\u00dfDagstuhl, Germany, 15\u201319 May 2000]","author":"Applegate","year":"2001"},{"key":"2026012711402475900_ref3","first-page":"2","article-title":"Polynomial time approximation schemes for Euclidean TSP and other geometric problems","volume-title":"Proceedings of the 37th Conference on Foundations of Computer Science","author":"Arora","year":"1996"},{"key":"2026012711402475900_ref4","doi-asserted-by":"crossref","first-page":"462","DOI":"10.1017\/S1471068417000102","article-title":"Constraint answer set solver ref4 and why integration schemas matter","volume":"17","author":"Balduccini","year":"2017","journal-title":"Theory and Practice of Logic Programming"},{"key":"2026012711402475900_ref5","first-page":"529","article-title":"System ASPMT2SMT: Computing ASPMT theories by SMT solvers","volume-title":"Proceedings of the 14th European Conference on Logics in Artificial Intelligence, JELIA 2014, Funchal, Madeira, Portugal, September 24\u201326, 2014","author":"Bartholomew","year":"2014"},{"key":"2026012711402475900_ref6","doi-asserted-by":"crossref","first-page":"97","DOI":"10.1016\/0895-7177(94)90127-9","article-title":"Introducing global constraints in CHIP","volume":"20","author":"Beldiceanu","year":"1994","journal-title":"Mathematical and Computer Modelling"},{"key":"2026012711402475900_ref7","first-page":"318","article-title":"Improving the efficiency of Euclidean TSP solving in constraint programming by predicting effective nocrossing constraints","volume-title":"AIxIA 2020 - Advances in Artificial Intelligence - XIXth International Conference of the Italian Association for Artificial Intelligence, Virtual Event, November 25\u201327, 2020, Revised Selected Papers","author":"Bellodi","year":"2020"},{"key":"2026012711402475900_ref8","doi-asserted-by":"crossref","first-page":"205","DOI":"10.1007\/s10601-012-9119-x","article-title":"Improved filtering for weighted circuit constraints","volume":"17","author":"Benchimol","year":"2012","journal-title":"Constraints"},{"key":"2026012711402475900_ref9","first-page":"1412","article-title":"Improved filtering for the Euclidean traveling salesperson problem in CLP(FD)","volume-title":"The Thirty-Fourth AAAI Conference on Artificial Intelligence, AAAI 2020, the Thirty-Second Innovative Applications of Artificial Intelligence Conference, IAAI 2020, the Tenth AAAI Symposium on Educational Advances in Artificial Intelligence, EAAI 2020, New York, NY, USA, February 7\u201312, 2020","author":"Bertagnon","year":"2020"},{"key":"2026012711402475900_ref10","doi-asserted-by":"crossref","first-page":"1580","DOI":"10.1093\/logcom\/exae042","article-title":"ASPECT: answer set rePresentation as vEctor graphiCs in laTex","volume":"34","author":"Bertagnon","year":"2024","journal-title":"Journal of Logic and Computation"},{"key":"2026012711402475900_ref11","doi-asserted-by":"crossref","first-page":"139","DOI":"10.3233\/IA-240032","article-title":"Geometric reasoning on the euclidean traveling salesperson problem in answer set programming","volume":"18","author":"Bertagnon","year":"2024","journal-title":"Intelligenza Artificiale"},{"key":"2026012711402475900_ref12","first-page":"294","article-title":"ASP-Core-2 input language format. Theory Pract. Log","volume":"20","author":"Calimeri","year":"2020","journal-title":"Program."},{"key":"2026012711402475900_ref13","first-page":"316","article-title":"Solving small TSPs with constraints","volume-title":"Logic Programming, Proceedings of the Fourteenth International Conference on Logic Programming, Leuven, Belgium, July 8\u201311, 1997","author":"Caseau","year":"1997"},{"key":"2026012711402475900_ref14","first-page":"32","article-title":"The asymmetric traveling salesman problem: algorithms, instance generators, and tests","volume-title":"Algorithm Engineering and Experimentation, Third International Workshop, ALENEX 2001, Washington, DC, USA, January 5\u20136, 2001, Revised Papers","author":"Cirasella","year":"2001"},{"key":"2026012711402475900_ref15","doi-asserted-by":"crossref","first-page":"393","DOI":"10.1287\/opre.2.4.393","article-title":"Solution of a large-scale traveling-salesman problem","volume":"2","author":"Dantzig","year":"1954","journal-title":"Journal of the Operations Research Society of America"},{"key":"2026012711402475900_ref16","doi-asserted-by":"crossref","first-page":"141","DOI":"10.1016\/0020-0190(94)00071-9","article-title":"The convex-hull-and-line traveling salesman problem: A solvable case","volume":"51","author":"Deineko","year":"1994","journal-title":"Information Processing Letters"},{"key":"2026012711402475900_ref17","first-page":"170","article-title":"Learning heuristics for the TSP by policy gradient","volume-title":"Proceedings of the 15th International Conference on Integration of Constraint Programming, Artificial Intelligence, and Operations Research, CPAIOR 2018, Delft, The Netherlands, June 26\u201329, 2018","author":"Deudon","year":"2018"},{"key":"2026012711402475900_ref18","doi-asserted-by":"crossref","first-page":"465","DOI":"10.1017\/S1471068410000220","article-title":"A translational approach to constraint answer set solving","volume":"10","author":"Drescher","year":"2010","journal-title":"Theory and Practice of Logic Programming"},{"key":"2026012711402475900_ref19","first-page":"73","article-title":"Smodels with CLP and its applications: A simple and effective approach to aggregates in ASP","volume-title":"ICLP","author":"Elkabani","year":"2004"},{"key":"2026012711402475900_ref20","doi-asserted-by":"crossref","first-page":"278","DOI":"10.1016\/j.artint.2010.04.002","article-title":"Semantics and complexity of recursive aggregates in answer set programming","volume":"175","author":"Faber","year":"2011","journal-title":"Artificial Intelligence"},{"key":"2026012711402475900_ref21","doi-asserted-by":"crossref","DOI":"10.1002\/9780470050118.ecse226","article-title":"Answer set programming","volume-title":"Wiley Encyclopedia of Computer Science and Engineering","author":"Faber","year":"2008"},{"key":"2026012711402475900_ref22","doi-asserted-by":"crossref","first-page":"61","DOI":"10.1287\/opre.4.1.61","article-title":"The traveling-salesman problem","volume":"4","author":"Flood","year":"1956","journal-title":"Operations Research"},{"key":"2026012711402475900_ref23","doi-asserted-by":"crossref","first-page":"291","DOI":"10.1023\/A:1014492408220","article-title":"Embedding relaxations in global constraints for solving TSP and TSPTW","volume":"34","author":"Focacci","year":"2002","journal-title":"Annals of Mathematics and Artificial Intelligence"},{"key":"2026012711402475900_ref24","doi-asserted-by":"crossref","first-page":"403","DOI":"10.1287\/ijoc.14.4.403.2827","article-title":"A hybrid exact algorithm for the TSPTW","volume":"14","author":"Focacci","year":"2002","journal-title":"INFORMS Journal on Computing"},{"key":"2026012711402475900_ref25","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1007\/s10601-013-9148-0","article-title":"Explaining circuit propagation","volume":"19","author":"Francis","year":"2014","journal-title":"Constraints"},{"key":"2026012711402475900_ref26","first-page":"368","article-title":"Progress in ClaSP series 3","volume-title":"Proceedings of the 13th International Conference on Logic Programming and Nonmonotonic Reasoning, LPNMR 2015, Lexington, KY, USA, September 27\u201330, 2015","author":"Gebser","year":"2015"},{"key":"2026012711402475900_ref27","article-title":"Answer set solving in Practice","volume-title":"Synthesis Lectures on Artificial Intelligence and Machine Learning","author":"Gebser","year":"2012"},{"key":"2026012711402475900_ref28","first-page":"235","article-title":"Constraint answer set solving","volume-title":"Proceedings of the 25th International Conference on Logic Programming, ICLP 2009, Pasadena, CA, USA, July 14\u201317, 2009","author":"Gebser","year":"2009"},{"key":"2026012711402475900_ref29","first-page":"266","article-title":"Gringo: a new grounder for answer set programming","volume-title":"Proceedings of the 9th International Conference on Logic Programming and Nonmonotonic Reasoning, LPNMR 2007, Tempe, AZ, USA, May 15\u201317, 2007","author":"Gebser","year":"2007"},{"key":"2026012711402475900_ref30","first-page":"1070","article-title":"The stable model semantics for logic programming","volume-title":"ICLP","author":"Gelfond","year":"1988"},{"key":"2026012711402475900_ref31","doi-asserted-by":"crossref","first-page":"106","DOI":"10.1016\/S0377-2217(99)00284-2","article-title":"An effective implementation of the Lin-Kernighan traveling salesman heuristic","volume":"126","author":"Helsgaun","year":"2000","journal-title":"European Journal of Operational Research"},{"key":"2026012711402475900_ref32","doi-asserted-by":"crossref","first-page":"284","DOI":"10.1007\/978-3-030-30048-7_17","article-title":"Integration of structural constraints into TSP models","volume-title":"International Conference on Principles and Practice of Constraint Programming","author":"Isoart","year":"2019"},{"key":"2026012711402475900_ref33","article-title":"Tight integration of non-ground answer set programming and satisfiability modulo theories","volume-title":"Working notes of the 1st Workshop on Grounding and Transformations for Theories with Variables","author":"Janhunen","year":"2011"},{"key":"2026012711402475900_ref34","doi-asserted-by":"crossref","first-page":"872","DOI":"10.1017\/S1471068417000242","article-title":"Clingo goes linear constraints over reals and integers","volume":"17","author":"Janhunen","year":"2017","journal-title":"Theory and Practice of Logic Programming"},{"key":"2026012711402475900_ref35","doi-asserted-by":"crossref","first-page":"299","DOI":"10.1017\/S1471068421000508","article-title":"How to build your own ASP-based system?!","volume":"23","author":"Kaminski","year":"2023","journal-title":"Theory and Practice of Logic Programming"},{"key":"2026012711402475900_ref36","first-page":"706","article-title":"A filter for the circuit constraint","volume-title":"Proceedings of the 12th International Conference on Principles and Practice of Constraint Programming, CP 2006, Nantes, France, September 25\u201329, 2006","author":"Kaya","year":"2006"},{"key":"2026012711402475900_ref37","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1016\/j.artint.2013.10.004","article-title":"Relating constraint answer set programming languages and algorithms","volume":"207","author":"Lierler","year":"2014","journal-title":"Artificial Intelligence"},{"key":"2026012711402475900_ref38","doi-asserted-by":"crossref","first-page":"195","DOI":"10.1017\/S1471068421000478","article-title":"Constraint answer set programming: integrational and translational (or SMT-based) approaches","volume":"23","author":"Lierler","year":"2023","journal-title":"Theory and Practice of Logic Programming"},{"key":"2026012711402475900_ref39","doi-asserted-by":"crossref","first-page":"498","DOI":"10.1287\/opre.21.2.498","article-title":"An effective heuristic algorithm for the traveling-salesman problem","volume":"21","author":"Lin","year":"1973","journal-title":"Operations Research"},{"key":"2026012711402475900_ref40","first-page":"32","article-title":"Answer set programming via mixed integer programming","volume-title":"Proceedings of the 13th International Conference on Principles of Knowledge Representation and Reasoning","author":"Liu","year":"2012"},{"key":"2026012711402475900_ref41","doi-asserted-by":"crossref","first-page":"251","DOI":"10.1007\/s10472-009-9116-y","article-title":"Integrating answer set programming and constraint logic programming","volume":"53","author":"Mellarkod","year":"2008","journal-title":"Annals of Mathematics and Artificial Intelligence"},{"key":"2026012711402475900_ref42","doi-asserted-by":"crossref","first-page":"326","DOI":"10.1145\/321043.321046","article-title":"Integer programming formulation of traveling salesman problems","volume":"7","author":"Miller","year":"1960","journal-title":"Journal of the ACM"},{"key":"2026012711402475900_ref43","doi-asserted-by":"crossref","first-page":"1298","DOI":"10.1137\/S0097539796309764","article-title":"Guillotine subdivisions approximate polygonal subdivisions: A simple polynomial-time approximation scheme for geometric TSP, k-MST, and related problems","volume":"28","author":"Mitchell","year":"1999","journal-title":"SIAM Journal on Computing"},{"key":"2026012711402475900_ref44","doi-asserted-by":"crossref","first-page":"12","DOI":"10.1287\/trsc.32.1.12","article-title":"An exact constraint logic programming algorithm for the traveling salesman problem with time windows","volume":"32","author":"Pesant","year":"1998","journal-title":"Transportation Science"},{"key":"2026012711402475900_ref45","doi-asserted-by":"crossref","DOI":"10.3390\/a16040216","article-title":"Solving an industrial-scale warehouse delivery problem with answer set programming modulo difference constraints","volume":"16","author":"Rajaratnam","year":"2023","journal-title":"Algorithms"},{"key":"2026012711402475900_ref46","first-page":"362","article-title":"A filtering algorithm for constraints of difference in CSPs","volume-title":"Proceedings of the 12th National Conference on Artificial Intelligence, Seattle, WA, USA, July 31 - August 4, 1994","author":"R\u00e9gin","year":"1994"},{"key":"2026012711402475900_ref47","first-page":"67","article-title":"SMT-based constraint answer set solver EZSMT+ for non-tight programs","volume-title":"Proceedings of the Sixteenth International Conference on Principles of Knowledge Representation and Reasoning, KR 2018, Tempe, Arizona, 30 October - 2 November 2018","author":"Shen"},{"key":"2026012711402475900_ref48","first-page":"153","article-title":"The IDP system: a model expansion system for an extension of classical logic","volume-title":"Proceedings of Workshop on Logic and Search, Computation of Structures from Declarative Descriptions (LaSh)","author":"Wittocx","year":"2008"}],"container-title":["Journal of Logic and Computation"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/academic.oup.com\/logcom\/article-pdf\/36\/2\/exaf072\/66591318\/exaf072.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"syndication"},{"URL":"https:\/\/academic.oup.com\/logcom\/article-pdf\/36\/2\/exaf072\/66591318\/exaf072.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,1,27]],"date-time":"2026-01-27T16:40:37Z","timestamp":1769532037000},"score":1,"resource":{"primary":{"URL":"https:\/\/academic.oup.com\/logcom\/article\/doi\/10.1093\/logcom\/exaf072\/8442320"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2026,1,26]]},"references-count":48,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2026,1,26]]}},"URL":"https:\/\/doi.org\/10.1093\/logcom\/exaf072","relation":{},"ISSN":["0955-792X","1465-363X"],"issn-type":[{"value":"0955-792X","type":"print"},{"value":"1465-363X","type":"electronic"}],"subject":[],"published-other":{"date-parts":[[2026,3]]},"published":{"date-parts":[[2026,1,26]]},"article-number":"exaf072"}}