A GPU implementation of large neighborhood search for solving constraint optimization problems

F. Campeotto, A. Dovier, F. Fioretto, E. Pontelli

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

18 Scopus citations

Abstract

Constraint programming has gained prominence as an effective and declarative paradigm for modeling and solving complex combinatorial problems. Techniques based on local search have proved practical to solve real-world problems, providing a good compromise between optimality and efficiency. In spite of the natural presence of concurrency, there has been relatively limited effort to use novel massively parallel architectures, such as those found in modern Graphical Processing Units (GPUs), to speedup local search techniques in constraint programming. This paper describes a novel framework which exploits parallelism from a popular local search method (the Large Neighborhood Search method), using GPUs.

Original languageEnglish (US)
Title of host publicationECAI 2014 - 21st European Conference on Artificial Intelligence, Including Prestigious Applications of Intelligent Systems, PAIS 2014, Proceedings
EditorsTorsten Schaub, Gerhard Friedrich, Barry O'Sullivan
PublisherIOS Press
Pages189-194
Number of pages6
ISBN (Electronic)9781614994183
DOIs
StatePublished - 2014
Event21st European Conference on Artificial Intelligence, ECAI 2014 - Prague, Czech Republic
Duration: Aug 18 2014Aug 22 2014

Publication series

NameFrontiers in Artificial Intelligence and Applications
Volume263
ISSN (Print)0922-6389

Conference

Conference21st European Conference on Artificial Intelligence, ECAI 2014
CountryCzech Republic
CityPrague
Period8/18/148/22/14

ASJC Scopus subject areas

  • Artificial Intelligence

Fingerprint Dive into the research topics of 'A GPU implementation of large neighborhood search for solving constraint optimization problems'. Together they form a unique fingerprint.

  • Cite this

    Campeotto, F., Dovier, A., Fioretto, F., & Pontelli, E. (2014). A GPU implementation of large neighborhood search for solving constraint optimization problems. In T. Schaub, G. Friedrich, & B. O'Sullivan (Eds.), ECAI 2014 - 21st European Conference on Artificial Intelligence, Including Prestigious Applications of Intelligent Systems, PAIS 2014, Proceedings (pp. 189-194). (Frontiers in Artificial Intelligence and Applications; Vol. 263). IOS Press. https://doi.org/10.3233/978-1-61499-419-0-189