A Heuristic Restart Strategy to Speed Up the Solving of Satisfiability Problem

Restart strategies are widely used in today´s conflict-driven clause learning SAT solvers, such as fixed-interval policy, geometric policy, Luby´s policy, nested restart scheme, adaptive restart strategy, counter implication restart and so on. It has been demonstrated that appropriate use of restarts can improve the speed of SAT solvers tremendously. Growing numbers of studies have been beginning to pay attention to restart strategies, from triggering a restart to selecting the first decision after a restart. However, the number of restarts, an important state parameter of SAT solver, has never gotten any attention before. This paper introduces a novel heuristic method of decision-making after a restart by making full use of the number of each variable´s restart times, which is named VRT restart strategy in this paper. We integrated it into a modern SAT solver. Experimental results show that the solver with our strategy is considerably faster than the original one.