Adaptive Parallelization for Constraint Satisfaction Search

This paper introduces two adaptive paradigms that parallelize search for solutions to constraint satisfaction problems. Both are intended for any sequential solver that uses contention-oriented variable-ordering heuristics and restart strategies. Empirical results demonstrate that both paradigms improve the search performance of an underlying sequential solver, and also solve challenging problems left open after recent solver competitions.

Authors

• Xi Yun
• Susan L. Epstein

Keywords

• constraint satisfaction processing
• adaptive parallelized search
• dynamic workload balance