Graphics processing units (GPUs) have achieved remarkable success in accelerating machine learning workloads, particularly for training and inference tasks. However, similar performance gains have not yet been fully realized in the domain of general and exact combinatorial optimization. Existing GPU-based approaches in this area have mainly focused on metaheuristic methods or exact solvers restricted to specific problem classes. A notable recent advance has occurred in linear programming, where GPU efficiency has been unlocked through algorithms such as the primal–dual hybrid gradient method, which relies heavily on matrix operations and has been successfully applied to mixed-integer linear programming.
In contrast, constraint programming (CP), which supports non-linear constraints and provides exact solutions through constraint propagation and backtracking search, has seen limited progress on GPU architectures. Previous efforts have either restricted the expressiveness of constraint languages, offloaded only selected computations to the GPU, or focused on specific types of constraints. While promising, these approaches do not yet support a general-purpose, fully GPU-based constraint programming solver.
Building on recent advances in concurrent constraint programming, this work introduces Turbo, a general and exact discrete constraint programming solver designed specifically for GPU architectures. Turbo implements both constraint propagation and backtracking search entirely on the GPU. The solver is based on integer interval bound propagation and decomposes constraint networks into ternary constraint networks (TCNs), enabling efficient parallel propagation following the parallel CCP computation model. This representation allows for optimized memory access patterns and improved parallel efficiency on GPUs.
Due to hardware constraints, Turbo adopts a simplified solver architecture compared to state-of-the-art CPU-based constraint solvers and does not include advanced features such as global constraints, learning mechanisms, restart strategies, or domain consistency. Despite this simplicity, Turbo achieves competitive performance on benchmark problems. Experimental results on the MiniZinc 2024 Challenge demonstrate that Turbo is able to match or outperform established sequential solvers on a substantial portion of instances. A comprehensive experimental evaluation is presented to assess the effectiveness and scalability of the proposed approach.
TY - BOOKAU - Talbot, PierrePY - 2026/01/22SP - T1 - A GPU-based Constraint Programming SolverVL - ER -
Link to full paper:
https://www.researchgate.net/publication/399606771_A_GPU-based_Constraint_Programming_Solver
