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 in questo prodotto:
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.

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/11390/1293205
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 0
  • ???jsp.display-item.citation.isi??? 0
social impact