The Cumulative constraint is a foundamental global constraint, which naturally arises in a variety of problems related to scheduling with limited resources. Since its introduction, numerous propagation algorithms have been proposed, offering different tradeoffs between computational complexity and filtering power. Such diversity allows the resolution of a wide range of applications. Motivated by the impressive computational power that modern Graphical Processing Units (GPUs) provide, this paper explores the use of GPUs for the propagation of the Cumulative constraint. The paper describes the development of a GPU-Acceletated Propagator (GAP), motivates the design choices, and provides solutions for several design challenges. The implementation is evaluated in comparison with state-of-the-art constraint solvers on different benchmarks from the literature. The results suggest that our approach is competitive, providing strong filtering in a reasonable amount of time.
Constraint propagation on GPU: a case study for the cumulative constraint
Dovier A.;Formisano A.;
2024-01-01
Abstract
The Cumulative constraint is a foundamental global constraint, which naturally arises in a variety of problems related to scheduling with limited resources. Since its introduction, numerous propagation algorithms have been proposed, offering different tradeoffs between computational complexity and filtering power. Such diversity allows the resolution of a wide range of applications. Motivated by the impressive computational power that modern Graphical Processing Units (GPUs) provide, this paper explores the use of GPUs for the propagation of the Cumulative constraint. The paper describes the development of a GPU-Acceletated Propagator (GAP), motivates the design choices, and provides solutions for several design challenges. The implementation is evaluated in comparison with state-of-the-art constraint solvers on different benchmarks from the literature. The results suggest that our approach is competitive, providing strong filtering in a reasonable amount of time.File | Dimensione | Formato | |
---|---|---|---|
Constraint propagation on GPU_ a case study for the Cumulative constraint.pdf
non disponibili
Licenza:
Non pubblico
Dimensione
1.46 MB
Formato
Adobe PDF
|
1.46 MB | Adobe PDF | Visualizza/Apri Richiedi una copia |
I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.