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

被引：1

作者：

Guo, Ying ^{[1
]}

Zhang, Bin ^{[1
]}

Zhang, Changsheng ^{[1
]}

机构：

[1] Northeastern Univ, Coll Informat Sci & Engn, Shenyang, Peoples R China

来源：

2012 FIFTH INTERNATIONAL SYMPOSIUM ON COMPUTATIONAL INTELLIGENCE AND DESIGN (ISCID 2012), VOL 2 | 2012年

关键词：

Satisfiability Problem; SAT solver; restart strategy; variable's restart times; SAT-SOLVER;

D O I：

10.1109/ISCID.2012.254

中图分类号：

TP18 [人工智能理论];

学科分类号：

081104 ; 0812 ; 0835 ; 1405 ;

摘要：

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.

引用

页码：423 / 426

页数：4

共 15 条

[11] Joao M., 1999, IEEE T COMPUT, V48, P506, DOI [10.1109/12.769433, DOI 10.1109/12.769433]
[12] OPTIMAL SPEEDUP OF LAS-VEGAS ALGORITHMS
LUBY, M
SINCLAIR, A
ZUCKERMAN, D
[J]. INFORMATION PROCESSING LETTERS, 1993, 47 (04) : 173 - 180
[13] Moskewicz MW, 2001, DES AUT CON, P530, DOI 10.1109/DAC.2001.935565
[14] Ramos A, 2011, LECT NOTES COMPUT SC, V6695, P216
[15] van der Tak P., 2011, J SATISFIABILITY BOO, P133

← 1 2 →