Abstract
Constraint Programming (CP) solvers often struggle with heavy-tailed runtime distributions. While restarts are a standard mitigation technique, their parallelization has been under-explored compared to tree-based methods. This paper presents Parallel Luby Restarts (PLR), a deterministic scheduling approach that achieves near-linear speedups on multi-core systems by executing independent restarts in parallel.
Introduction
In Constraint Programming, search processes can frequently become trapped in large, fruitless subtrees, a phenomenon known as the "heavy-tail" effect. To combat this, solvers utilize restart strategies, where the search is periodically abandoned and restarted with a different random seed. While effective, sequential restarts do not leverage modern multi-core architectures. Traditional parallel search methods, which split the search tree, often suffer from high communication overhead and non-determinism. This work demonstrates that for solvers without "no-good learning," parallelizing the restarts themselves offers a simpler and more scalable path to performance.
Methodology: Parallel Luby Restarts
The proposed method, Parallel Luby Restarts (PLR), utilizes the Luby sequence—a mathematically optimal strategy for restart intervals (e.g., 1, 1, 2, 1, 1, 2, 4...). Because many CP solvers do not share information between restarts, each restart can be treated as an independent task.
The core of PLR is an Earliest-Start-Time-First scheduling algorithm. Each processor maintains a local copy of the Luby sequence and picks the next available restart based on its current accumulated workload (fail-limit). This ensures balanced utilization across cores. To maintain strict determinism, each restart index is paired with a unique, deterministic seed. The solver ensures that the solution returned is identical to a sequential run by waiting for earlier restarts in the sequence to finish if a later one finds a solution first.
Evaluation and Results
The researchers implemented PLR in the Gecode solver and tested it against several benchmarks, including Quasigroup Completion (QCP), Magic Squares, and the 2012 MiniZinc Challenge.
The results demonstrate impressive scalability. For instance, on Magic Square problems, the system achieved 88% efficiency on 32 cores. In cases involving heavy-tailed distributions, such as QCP, the method even yielded super-linear speedups, as the increased number of parallel restarts significantly raised the probability of finding a short solution path quickly. Furthermore, PLR proved more robust than Gecode's native tree-based parallelization, achieving a 35.7x speedup on 32 cores compared to the default's 2.27x on difficult MiniZinc instances.
Conclusion
Parallel Luby Restarts offer a powerful yet simple mechanism for parallelizing CP solvers. By focusing on the independence of restarts, the method avoids the complexities of tree-based parallelization while providing the deterministic results required for industrial use. Future work will investigate how to incorporate localized learning within this parallel framework to further enhance search efficiency.
Summary updated