Comparative Analysis of Restart Strategy of Satisfiability Problem Solver
Yin Guo · Journal of Chinese Computer Systems · 2013
It has been proved that the introduction of restart can greatly improve solving performance in the SAT solver,and many different restart strategies appear accordingly. However,no comprehensive comparative analysis has been made for them currently. To avoid the arbitrariness of the restart strategy selection and inspire the designing of better restart strategy,seven representative restart strategies are selected to make a series of experimental comparative analysis. We take Minisat which is currently widely used as the basic solver,and take some application benchmarks from the international SAT 2011 competition as our testing cases. The experimental results show that( i) restart strategy can enormously impact on the solving process and performance of SAT solver;( ii) the geometric sequence scheduling strategy is superior to other strategies at average comprehensive performance with respect to application benchmarks;( iii) within limits,the solving performance may be better if the restart frequency is greater;( iv) the restart frequency with incremental changes can avoid leading to incomplete search.