Parallel Restarted Search

Authors

  • Andre Cire Carnegie Mellon University
  • Serdar Kadioglu Oracle America Inc.
  • Meinolf Sellmann IBM Research

DOI:

https://doi.org/10.1609/aaai.v28i1.8848

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.

Downloads

Published

2014-06-21

How to Cite

Cire, A., Kadioglu, S., & Sellmann, M. (2014). Parallel Restarted Search. Proceedings of the AAAI Conference on Artificial Intelligence, 28(1). https://doi.org/10.1609/aaai.v28i1.8848

Issue

Section

AAAI Technical Track: Heuristic Search and Optimization