A Heuristic Restart Strategy to Speed Up the Solving of Satisfiability Problem
Restart strategies are widely used in todays conflict-driven clause learning SAT solvers, such as fixed-interval policy, geometric policy, Lubys 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 decisionmaking after a restart by making full use of the number of each variables 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.
Satisfiability Problem SAT solver restart strategy variables restart times
Ying Guo Bin Zhang Changsheng Zhang
College of Information Science and Engineering Northeastern University Shenyang, China
国际会议
杭州
英文
1001-1004
2012-10-28（万方平台首次上网日期，不代表论文的发表时间）