Parallelizing constraint programming with learning

Thorsten Ehlers, Peter J. Stuckey

Research output: Chapter in Book/Report/Conference proceedingConference PaperResearchpeer-review

3 Citations (Scopus)

Abstract

Parallel Constraint Programming (CP) solvers typically split the search space in disjoint subspaces, and run solvers independently on these. This may induce significant overhead when solving optimization problems. Parallel Boolean Satisfiability (SAT) solvers typically run a portfolio of solvers, all solving the same problem but sharing some limited learnt clause information. In this paper we consider parallelizing a lazy clause generation (LCG) constraint programming solver, which is a constraint programming solver with learning. Since it is both a kind of CP solver and a kind of SAT solver it is not clear which approach to parallelization is likely to be most effective. We give examples of very different kinds of optimization problems we wish to parallelize and show that a hybrid approach to parallelization can provide a robust and high performing parallel LCG solver.

Original languageEnglish
Title of host publicationIntegration of AI and OR Techniques in Constraint Programming
Subtitle of host publication13th International Conference, CPAIOR 2016 Banff, AB, Canada, May 29 – June 1, 2016 Proceedings
EditorsClaude-Guy Quimper
Place of PublicationCham Switzerland
PublisherSpringer
Pages142-158
Number of pages17
ISBN (Electronic)9783319339542
ISBN (Print)9783319339535
DOIs
Publication statusPublished - 2016
Externally publishedYes
EventInternational Conference on Integration of Artificial Intelligence and Operations Research Techniques in Constraint Programming for Combinatorial Optimization Problems 2016 - Banff, Canada
Duration: 29 May 20161 Jun 2016
Conference number: 13th
https://symposia.cirrelt.ca/CPAIOR2016/en/home (Conference website)
https://link.springer.com/book/10.1007/978-3-319-33954-2 (Proceedings)

Publication series

NameLecture Notes in Computer Science
PublisherSpringer
Volume9676
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Conference

ConferenceInternational Conference on Integration of Artificial Intelligence and Operations Research Techniques in Constraint Programming for Combinatorial Optimization Problems 2016
Abbreviated titleCPAIOR 2016
CountryCanada
CityBanff
Period29/05/161/06/16
Internet address

Cite this