Exploiting GPUs in solving (distributed) constraint optimization problems with dynamic programming

Ferdinando Fioretto, Tiep Le, Enrico Pontelli, William Yeoh, Tran Cao Son

Research output: Chapter in Book/Report/Conference proceedingConference contribution

9 Scopus citations

Abstract

This paper proposes the design and implementation of a dynamic programming based algorithm for (distributed) constraint optimization, which exploits modern massively parallel architectures, such as those found in modern Graphical Processing Units (GPUs). The paper studies the proposed algorithm in both centralized and distributed optimization contexts. The experimental analysis, performed on unstructured and structured graphs, shows the advantages of employing GPUs, resulting in enhanced performances and scalability.

Original languageEnglish (US)
Title of host publicationPrinciples and Practice of Constraint Programming - 21st International Conference, CP 2015, Proceedings
EditorsGilles Pesant
PublisherSpringer Verlag
Pages121-139
Number of pages19
ISBN (Print)9783319232188
DOIs
StatePublished - 2015
Event21st International Conference on the Principles and Practice of Constraint Programming, CP 2015 - Cork, Ireland
Duration: Aug 31 2015Sep 4 2015

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume9255
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Conference

Conference21st International Conference on the Principles and Practice of Constraint Programming, CP 2015
CountryIreland
CityCork
Period8/31/159/4/15

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Computer Science(all)

Fingerprint Dive into the research topics of 'Exploiting GPUs in solving (distributed) constraint optimization problems with dynamic programming'. Together they form a unique fingerprint.

  • Cite this

    Fioretto, F., Le, T., Pontelli, E., Yeoh, W., & Son, T. C. (2015). Exploiting GPUs in solving (distributed) constraint optimization problems with dynamic programming. In G. Pesant (Ed.), Principles and Practice of Constraint Programming - 21st International Conference, CP 2015, Proceedings (pp. 121-139). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 9255). Springer Verlag. https://doi.org/10.1007/978-3-319-23219-5_9