A GPU-based Constraint Programming Solver

[en] Machine learning has tremendously benefited from graphics processing units (GPUs) to accelerate training and inference by several orders of magnitude. However, this success has not been replicated in general and exact combinatorial optimization. Our key contribution is to propose a general-purpose discrete constraint programming solver fully implemented on GPU. It is based on integer interval bound propagation and backtracking search. The two main ingredients are (1) ternary constraint network optimized for GPU architectures, and (2) an on-demand subproblems generation strategy. Our constraint solving algorithm is significantly simpler than those found in optimized CPU constraint solvers, yet is competitive with sequential solvers in the MiniZinc 2024 challenge.

Disciplines :

Computer science

Author, co-author :

TALBOT, Pierre ; University of Luxembourg > Faculty of Science, Technology and Medicine (FSTM) > Department of Computer Science (DCS)

External co-authors :

Language :

English

Title :

A GPU-based Constraint Programming Solver

Publication date :

14 March 2026

Journal title :

Proceedings of the AAAI Conference on Artificial Intelligence

ISSN :

2159-5399

eISSN :

2374-3468

Publisher :

Association for the Advancement of Artificial Intelligence (AAAI)

Volume :

Issue :

Pages :

14331-14341

Peer reviewed :

Peer Reviewed verified by ORBi

Additional URL :

https://ojs.aaai.org/index.php/AAAI/article/download/38448/42410

FnR Project :

FNR16101289 - COMOC - A Concurrent Model Of Computation For Trustworthy Gpu Programming, 2021 (01/01/2022-31/12/2024) - Pascal Bouvry

Name of the research project :

U-AGR-7091 - C21/IS/16101289/COMOC/Bouvry - TALBOT Pierre

Funders :

FNR - Fonds National de la Recherche

Funding number :

C21/IS/16101289

Available on ORBilu :

since 19 March 2026

Statistics

Number of views

33 (4 by Unilu)

Number of downloads

10 (2 by Unilu)

More statistics

Scopus citations^®

Scopus citations^®
without self-citations

OpenCitations

OpenAlex citations

Bibliography

Abbas, A.; and Swoboda, P. 2022. FastDOG: Fast Discrete Optimization on GPU. In 2022 IEEE/CVF Conference on Computer Vision and Pattern Recognition (CVPR), 439– 449. New Orleans, LA, USA: IEEE. ISBN 978-1-66546-946-3.
Applegate, D.; Díaz, M.; Hinder, O.; Lu, H.; Lubin, M.; O’Donoghue, B.; and Schudy, W. 2021. Practical large-scale linear programming using primal-dual hybrid gradient. Advances in Neural Information Processing Systems, 34: 20243–20257.
Apt, K. R. 1999. The essence of constraint propagation. Theoretical computer science, 221(1-2): 179–210.
Arbelaez, A.; and Codognet, P. 2014. A GPU Implementation of Parallel Constraint-Based Local Search. In 2014 22nd Euromicro International Conference on Parallel, Distributed, and Network-Based Processing, 648–655. Torino, Italy: IEEE. ISBN 978-1-4799-2729-6.
Audemard, G.; Boussemart, F.; Lecoutre, C.; Piette, C.; and Roussel, O. 2020. XCSP3 and its ecosystem. Constraints.
Benhamou, F.; Goualard, F.; Granvilliers, L.; and Puget, J.-F. 1999. Revising hull and box consistency. In Proceedings of the 1999 International Conference on Logic Programming, 230–244. USA: Massachusetts Institute of Technology. ISBN 0262541041.
Benhamou, F.; and Older, W. J. 1997. Applying interval arithmetic to real, integer, and boolean constraints. The Journal of Logic Programming, 32(1): 1 – 24.
Boussemart, F.; Hemery, F.; Lecoutre, C.; and Sais, L. 2004. Boosting systematic search by weighting constraints. In ECAI, volume 16, 96–97.
Campeotto, F.; Dal Palu, A.; Dovier, A.; Fioretto, F.; and Pontelli, E. 2014. Exploring the use of GPUs in constraint solving. In International Symposium on Practical Aspects of Declarative Languages, 152–167. Springer.
Cappart, Q.; Moisan, T.; Rousseau, L.-M.; Prémont-Schwarz, I.; and Cire, A. A. 2021. Combining reinforcement learning and constraint programming for combinatorial optimization. In Proceedings of the AAAI conference on artificial intelligence, volume 35, 3677–3687.
Chambolle, A.; and Pock, T. 2011. A First-Order Primal-Dual Algorithm for Convex Problems with Applications to Imaging. Journal of Mathematical Imaging and Vision, 40(1): 120–145.
Codognet, P.; and Diaz, D. 1996. Compiling constraints in clp(FD). The Journal of Logic Programming, 27(3): 185 – 226.
Correia, M.; and Barahona, P. 2013. View-based propagation of decomposable constraints. Constraints, 18(4): 579– 608.
Dovier, A.; Formisano, A.; Pontelli, E.; and Tardivo, F. 2021. {CUDA}: Set Constraints on GPUs. 28.
Essaid, M.; Idoumghar, L.; Lepagnot, J.; and Brévilliers, M. 2019. GPU parallelization strategies for metaheuristics: a survey. International Journal of Parallel, Emergent and Distributed Systems, 34(5): 497–522.
Gent, I. P.; Miguel, I.; Nightingale, P.; McCreesh, C.; Prosser, P.; Moore, N. C.; and Unsworth, C. 2018. A review of literature on parallel constraint solving. Theory and Practice of Logic Programming, 18(5-6): 725–758.
Gmys, J. 2022. Exactly Solving Hard Permutation Flow-shop Scheduling Problems on Peta-Scale GPU-Accelerated Supercomputers. INFORMS Journal on Computing, 34(5): 2502–2522.
Gmys, J.; Mezmaz, M.; Melab, N.; and Tuyttens, D. 2016. A GPU-based Branch-and-Bound algorithm using Integer–Vector–Matrix data structure. Parallel Computing, 59: 119–139.
Gupta, G.; Pontelli, E.; Ali, K. A.; Carlsson, M.; and Hermenegildo, M. V. 2001. Parallel execution of Prolog programs: a survey. ACM Transactions on Programming Languages and Systems (TOPLAS), 23(4): 472–602.
Hamadi, Y.; and Sais, L., eds. 2018. Handbook of Parallel Constraint Reasoning. Cham: Springer International Publishing. ISBN 978-3-319-63515-6 978-3-319-63516-3.
Heule, M. J.; Kullmann, O.; and Marek, V. W. 2017. Solving Very Hard Problems: Cube-and-Conquer, a Hybrid SAT Solving Method. In Proceedings of the Twenty-Sixth International Joint Conference on Artificial Intelligence, IJCAI-17, 4864–4868.
Hijma, P.; Heldens, S.; Sclocco, A.; Van Werkhoven, B.; and Bal, H. E. 2023. Optimization Techniques for GPU Programming. ACM Computing Surveys, 55(11): 1–81.
Huang, B.; Cheng, R.; Li, Z.; Jin, Y.; and Tan, K. C. 2024. EvoX: A distributed GPU-accelerated framework for scalable evolutionary computation. IEEE Transactions on Evolutionary Computation. Publisher: IEEE.
Krizhevsky, A.; Sutskever, I.; and Hinton, G. E. 2012. Imagenet classification with deep convolutional neural networks. Advances in neural information processing systems, 25.
Lecoutre, C. 2009. Constraint networks: techniques and algorithms. Hoboken, NJ: ISTE/John Wiley. ISBN 978-1-84821-106-3.
Mackworth, A. K. 1977. Consistency in networks of relations. Artificial intelligence, 8(1): 99–118.
Malapert, A.; Régin, J.-C.; and Rezgui, M. 2016. Embarrassingly Parallel Search in Constraint Programming. Journal of Artificial Intelligence Research, 57: 421–464.
NVIDIA Corporation. 2025a. CUDA Toolkit Documentation. https://docs.nvidia.com/cuda/. Accessed: 2025-11-10.
NVIDIA Corporation. 2025b. NVIDIA cuOpt. https://docs.nvidia.com/cuopt/user-guide/latest/. Accessed: 2025-11-10.
Ohrimenko, O.; Stuckey, P. J.; and Codish, M. 2009. Propagation via Lazy Clause Generation. Constraints, 14(3): 357– 391.
Perron, L. 1999. Search procedures and parallelism in constraint programming. In International Conference on Principles and Practice of Constraint Programming, 346–360. Springer.
Perron, L.; and Didier, F. 2025. CP-SAT (v9.9). https://developers.google.com/optimization/cp/cp solver/. Accessed: 2025-12-27.
Prud’homme, C.; and Fages, J.-G. 2022. Choco-solver: A Java library for constraint programming. Journal of Open Source Software, 7(78): 4708.
Sam-Haroud, D.; and Faltings, B. 1996. Consistency techniques for continuous constraints. Constraints, 1(1): 85– 118.
Saraswat, V. A.; Rinard, M.; and Panangaden, P. 1991. The Semantic Foundations of Concurrent Constraint Programming. In Proceedings of the 18th ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages, POPL ’91, 333–352. New York, NY, USA: ACM. ISBN 0-89791-419-8.
Schulte, C. 1999. Comparing trailing and copying for constraint programming. In In Proceedings of the International Conference on Logic Programming, 275–289. The MIT Press.
Schulte, C. 2000. Parallel search made simple. In Proceedings of TRICS: Techniques foR Implementing Constraint programming Systems, a post-conference workshop of CP, 41–57.
Schulte, C.; and Stuckey, P. J. 2008. Efficient Constraint Propagation Engines. ACM Trans. Program. Lang. Syst., 31(1): 2:1–2:43.
Schulte, C.; and Tack, G. 2013. View-based propagator derivation. Constraints, 18(1): 75–107.
Schulte, C.; Tack, G.; and Lagerkvist, M. 2020. Modeling and Programming with Gecode.
Sofranac, B.; Gleixner, A.; and Pokutta, S. 2022. Accelerating domain propagation: An efficient GPU-parallel algorithm over sparse matrices. Parallel Computing, 109: 102874.
Stuckey, P. J.; Feydy, T.; Schutt, A.; Tack, G.; and Fischer, J. 2014. The MiniZinc challenge 2008–2013. AI Magazine, 35(2): 55–60.
Tack, G. 2009. Constraint Propagation – Models, Techniques, Implementation. Ph.D. thesis, Saarland University.
Talbot, P. 2025. Decomposition and Preprocessing of Ternary Constraint Networks. arXiv preprint arXiv:2511.11872.
Talbot, P.; Pinel, F.; and Bouvry, P. 2022. A Variant of Concurrent Constraint Programming on GPU. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 36, 3830–3839.
Tang, Y.; Tian, Y.; and Ha, D. 2022. Evojax: Hardware-accelerated neuroevolution. In Proceedings of the Genetic and Evolutionary Computation Conference Companion, 308–311.
Tardivo, F.; Dovier, A.; Formisano, A.; Michel, L.; and Pontelli, E. 2023. Constraint propagation on GPU: A case study for the AllDifferent constraint. Journal of Logic and Computation, 33(8): 1734–1752.
Tardivo, F.; Dovier, A.; Formisano, A.; Michel, L.; and Pontelli, E. 2024. Constraint propagation on GPU: A case study for the cumulative constraint. Constraints, 29: 192–214. Publisher: Springer.
Van Hentenryck, P. 1989. Constraint Satisfaction in Logic Programming. MIT Press. ISBN 0-262-08181-4.
Wen-mei W. Hwu and David B. Kirk and Izzat El Hajj. 2023. Programming Massively Parallel Processors (Fourth Edition). Morgan Kaufmann. ISBN 9780323912310.
Zhang, G.; Feng, W.; and Cagan, J. 2023. A GPU-Based Parallel Region Classification Method for Continuous Constraint Satisfaction Problems. Journal of Mechanical Design, 146(4): 041705.