Diversification and Intensification in Parallel SAT Solving

In this paper, we explore the two well-known principles of diversification and intensification in portfolio-based parallel SAT solving. These dual concepts play an important role in several search algorithms including local search, and appear to be a key point in modern parallel SAT solvers. To study their tradeoff, we define two roles for the computational units. Some of them classified as

Masters

perform an original search strategy, ensuring diversification. The remaining units, classified as

Slaves

are there to intensify their master’s strategy. Several important questions have to be answered. The first one is what information should be given to a slave in order to intensify a given search effort? The second one is, how often, a subordinated unit has to receive such information? Finally, the question of finding the number of subordinated units and their connections with the search efforts has to be answered. Our results lead to an original intensification strategy which outperforms the best parallel SAT solver ManySAT, and solves some open SAT instances.