{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,24]],"date-time":"2025-10-24T13:00:24Z","timestamp":1761310824615,"version":"build-2065373602"},"reference-count":21,"publisher":"Cambridge University Press (CUP)","issue":"4","license":[{"start":{"date-parts":[[2025,8,28]],"date-time":"2025-08-28T00:00:00Z","timestamp":1756339200000},"content-version":"unspecified","delay-in-days":58,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"content-domain":{"domain":["cambridge.org"],"crossmark-restriction":true},"short-container-title":["Theory and Practice of Logic Programming"],"published-print":{"date-parts":[[2025,7]]},"abstract":"<jats:title>Abstract<\/jats:title>\n                  <jats:p>Constraint Programming developed within Logic Programming in the Eighties; nowadays all Prolog systems encompass modules capable of handling constraint programming on finite domains demanding their solution to a constraint solver. This work focuses on a specific form of constraint, the so-called table constraint, used to specify conditions on the values of variables as an enumeration of alternative options. Since every condition on a set of finite domain variables can be ultimately expressed as a finite set of cases, Table can, in principle, simulate any other constraint. These characteristics make Table one of the most studied constraints ever, leading to a series of increasingly efficient propagation algorithms. Despite this, it is not uncommon to encounter real-world problems with hundreds or thousands of valid cases that are simply too many to be handled effectively with standard CPU-based approaches. In this paper, we deal with the Compact-Table (CT) algorithm, the state-of-the-art propagation algorithms for Table. We describe how CT can be enhanced by exploiting the massive computational power offered by modern Graphics Processing Units (GPUs)\u00a0to handle large Table constraints. In particular, we report on the design and implementation of GPU-accelerated CT, on its integration into an existing constraint solver, and on an experimental validation performed on a significant set of instances.<\/jats:p>","DOI":"10.1017\/s1471068425100197","type":"journal-article","created":{"date-parts":[[2025,8,28]],"date-time":"2025-08-28T08:35:43Z","timestamp":1756370143000},"page":"756-774","update-policy":"https:\/\/doi.org\/10.1017\/policypage","source":"Crossref","is-referenced-by-count":0,"title":["GPU Accelerated Compact-Table Propagation"],"prefix":"10.1017","volume":"25","author":[{"ORCID":"https:\/\/orcid.org\/0009-0008-3556-7177","authenticated-orcid":false,"given":"ENRICO","family":"SANTI","sequence":"first","affiliation":[{"name":"University of Udine"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-2052-8593","authenticated-orcid":false,"given":"AGOSTINO","family":"DOVIER","sequence":"additional","affiliation":[{"name":"University of Udine"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-6755-9314","authenticated-orcid":false,"given":"ANDREA","family":"FORMISANO","sequence":"additional","affiliation":[{"name":"University of Udine"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-3328-2174","authenticated-orcid":false,"given":"FABIO","family":"TARDIVO","sequence":"additional","affiliation":[{"name":"New Mexico State University"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"56","published-online":{"date-parts":[[2025,8,28]]},"reference":[{"key":"S1471068425100197_ref16","doi-asserted-by":"publisher","DOI":"10.1093\/logcom\/exad033"},{"key":"S1471068425100197_ref8","doi-asserted-by":"publisher","DOI":"10.1017\/S1471068411000615"},{"key":"S1471068425100197_ref14","volume-title":"Foundations of Artificial Intelligence","volume":"2","author":"ROSSI","year":"2006"},{"key":"S1471068425100197_ref9","first-page":"531","volume-title":"Proc. of CP\u201920","volume":"12333","author":"GENTZEL","year":"2020"},{"key":"S1471068425100197_ref1","first-page":"1","volume-title":"International Arab Conference on Information Technology, ACIT 2018","author":"ASSI","year":"2018"},{"key":"S1471068425100197_ref4","first-page":"207","volume-title":"Proc. of CP\u201916","volume":"9892","author":"DEMEULENAERE","year":"2016"},{"key":"S1471068425100197_ref13","first-page":"606","volume-title":"Proc. of CP 2014","volume":"8656","author":"PEREZ","year":"2014"},{"key":"S1471068425100197_ref17","doi-asserted-by":"publisher","DOI":"10.1007\/s10601-024-09371-w"},{"key":"S1471068425100197_ref20","doi-asserted-by":"crossref","unstructured":"VERHAEGHE, H. , LECOUTRE, C. , DEVILLE, Y. and SCHAUS, P. 2017a. Extending compact-table to basic smart tables. In Proc. of CP\u201917, Beck, J. C., Ed. Notes, Lecture in Computer Science, Springer, Cham, Vol. 10416, 297\u2013307.","DOI":"10.1007\/978-3-319-66158-2_19"},{"key":"S1471068425100197_ref12","doi-asserted-by":"publisher","DOI":"10.1007\/s12532-020-00190-7"},{"key":"S1471068425100197_ref10","doi-asserted-by":"publisher","DOI":"10.1007\/s10601-011-9107-6"},{"volume-title":"Proc. of AAAI\u201917","year":"2017b","author":"VERHAEGHE","key":"S1471068425100197_ref21"},{"key":"S1471068425100197_ref5","doi-asserted-by":"publisher","DOI":"10.1017\/S1471068422000059"},{"key":"S1471068425100197_ref2","doi-asserted-by":"publisher","DOI":"10.1016\/j.dam.2014.10.001"},{"key":"S1471068425100197_ref19","unstructured":"TRAVASCI, S. , TARDIVO, F. AND FORMISANO, A. 2025. GPU-accelerated propagation for the stable marriage constraint. In Proceedings of the 40th Italian Conference on Computational Logic, Alghero, Italy, June 25-27, 2025, D. Guidotti, L. Pandolfo and L. Pulina, Eds. CEUR Workshop Proceedings. CEUR-WS.org, Aachen. Vol. 4003. https:\/\/ceur-ws.org\/Vol-4003"},{"key":"S1471068425100197_ref3","first-page":"744","volume-title":"Logic Programming, 24th International Conference, ICLP 2008, Udine, Italy, December 9\u201313 2008, Proceedings","volume":"5366","author":"CIPRIANO","year":"2008"},{"key":"S1471068425100197_ref7","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-20832-4_17"},{"key":"S1471068425100197_ref15","doi-asserted-by":"publisher","DOI":"10.1609\/aimag.v35i2.2539"},{"key":"S1471068425100197_ref6","doi-asserted-by":"publisher","DOI":"10.3233\/FI-2010-359"},{"key":"S1471068425100197_ref11","doi-asserted-by":"publisher","DOI":"10.1016\/j.artint.2014.12.002"},{"key":"S1471068425100197_ref18","unstructured":"TARDIVO, F. , MICHEL, L. AND PONTELLI, E. 2024b. CP for bin packing with multi-core and GPUs. In 30th International Conference on Principles and Practice of Constraint Programming, CP 2024, September 2-6, 2024, Girona, Spain, P. Shaw, Ed. LIPIcs, Schloss Dagstuhl - Leibniz-Zentrum f\u00fcr Informatik, Dagstuhl, Germany, 307, 28:1\u201328:19."}],"container-title":["Theory and Practice of Logic Programming"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.cambridge.org\/core\/services\/aop-cambridge-core\/content\/view\/S1471068425100197","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,10,24]],"date-time":"2025-10-24T12:56:31Z","timestamp":1761310591000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.cambridge.org\/core\/product\/identifier\/S1471068425100197\/type\/journal_article"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2025,7]]},"references-count":21,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2025,7]]}},"alternative-id":["S1471068425100197"],"URL":"https:\/\/doi.org\/10.1017\/s1471068425100197","relation":{},"ISSN":["1471-0684","1475-3081"],"issn-type":[{"type":"print","value":"1471-0684"},{"type":"electronic","value":"1475-3081"}],"subject":[],"published":{"date-parts":[[2025,7]]},"assertion":[{"value":"\u00a9 The Author(s), 2025. Published by Cambridge University Press","name":"copyright","label":"Copyright","group":{"name":"copyright_and_licensing","label":"Copyright and Licensing"}},{"value":"This is an Open Access article, distributed under the terms of the Creative Commons Attribution licence (https:\/\/creativecommons.org\/licenses\/by\/4.0\/), which permits unrestricted re-use, distribution and reproduction, provided the original article is properly cited.","name":"license","label":"License","group":{"name":"copyright_and_licensing","label":"Copyright and Licensing"}},{"value":"This content has been made available to all.","name":"free","label":"Free to read"}]}}