Parallel Restarted Search

André A. Ciré, Serdar Kadioglu, Meinolf Sellmann

AAAI 2014 pp. 842-848

doi:10.1609/AAAI.V28I1.8848 /aaai/2014/cire2014aaai-parallel/

Abstract

We consider the problem of parallelizing restarted backtrack search. With few notable exceptions, most commercial and academic constraint programming solvers do not learn no-goods during search. Depending on the branching heuristics used, this means that there are little to no side-effects between restarts, making them an excellent target for parallelization. We develop a simple technique for parallelizing restarted search deterministically and demonstrate experimentally that we can achieve near-linear speed-ups in practice.

PDF AAAI Semantic Scholar

Cite

Text

Ciré et al. "Parallel Restarted Search." AAAI Conference on Artificial Intelligence, 2014. doi:10.1609/AAAI.V28I1.8848

Markdown

[Ciré et al. "Parallel Restarted Search." AAAI Conference on Artificial Intelligence, 2014.](https://mlanthology.org/aaai/2014/cire2014aaai-parallel/) doi:10.1609/AAAI.V28I1.8848

BibTeX

@inproceedings{cire2014aaai-parallel,
  title     = {{Parallel Restarted Search}},
  author    = {Ciré, André A. and Kadioglu, Serdar and Sellmann, Meinolf},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year      = {2014},
  pages     = {842-848},
  doi       = {10.1609/AAAI.V28I1.8848},
  url       = {https://mlanthology.org/aaai/2014/cire2014aaai-parallel/}
}