Restart Strategy Selection Using Machine Learning Techniques

Date Added: Jul 2009
Format: PDF

Restart strategies are an important factor in the performance of conflict-driven Davis Putnam style SAT solvers. Selecting a good restart strategy for a problem instance can enhance the performance of a solver. Inspired by recent success applying machine learning techniques to predict the runtime of SAT solvers, the authors present a method which uses machine learning to boost solver performance through a smart selection of the restart strategy. Based on easy to compute features, they train both a satisfiability classifier and runtime models. They use these models to choose between restart strategies. They present experimental results comparing this technique with the most commonly used restart strategies. The results demonstrate that machine learning is effective in improving solver performance.