|
|||||
|
|
| Solving SAT problem by heuristic polarity decision-making algorithm | |
| 基金项目： | 国家自然科学基金;国家自然科学基金;中国博士后科学基金;上海市自然科学基金 |
| 摘 要： | This paper presents a heuristic polarity decision-making algorithm for solving Boolean satisfiability (SAT). The algorithm inherits many features of the current state-of-the-art SAT solvers, such as fast BCP, clause recording, restarts, etc. In addition, a preconditioning step that calculates the polarities of variables according to the cover distribution of Karnaugh map is introduced into DPLL procedure, which greatly reduces the number of conflicts in the search process. The proposed approach is implemented as a SAT solver named DiffSat. Experiments show that DiffSat can solve many "real-life" instances in a reasonable time while the best existing SAT solvers, such as Zchaff and MiniSat, cannot. In particular, DiffSat can solve every instance of Bart benchmark suite in less than 0.03 s while Zchaff and MiniSat fail under a 900 s time limit. Furthermore, DiffSat even outperforms the outstanding incomplete algorithm DLM in some instances. |
| 收稿时间： | 16 October 2006 |
| 修稿时间： | 13 April 2007 |
Solving SAT problem by heuristic polarity decision-making algorithm |
|
| Authors: | Jing MingE Zhou Dian Tang PuShan Zhou XiaoFang Zhang Hua |
| Affiliation: | 1. State Key Laboratory of ASIC & System, Microelectronics Department, Fudan University, Shanghai 201203, China 2. State Key Laboratory of ASIC & System, Microelectronics Department, Fudan University, Shanghai 201203, China; E. E. Department, the University of Texas at Dallas, TX 75083, USA 3. E. E. Department, the University of Texas at Dallas, TX 75083, USA |
| Abstract: | This paper presents a heuristic polarity decision-making algorithm for solving Boolean satisfiability (SAT). The algorithm inherits many features of the current state-of-the-art SAT solvers, such as fast BCP, clause recording, restarts, etc. In addition, a preconditioning step that calculates the polarities of variables according to the cover distribution of Karnaugh map is introduced into DPLL procedure, which greatly reduces the number of conflicts in the search process. The proposed approach is implemented as a SAT solver named DiffSat. Experiments show that DiffSat can solve many "real-life" instances in a reasonable time while the best existing SAT solvers, such as Zchaff and MiniSat, cannot. In particular, DiffSat can solve every instance of Bart benchmark suite in less than 0.03 s while Zchaff and MiniSat fail under a 900 s time limit. Furthermore, DiffSat even outperforms the outstanding incomplete algorithm DLM in some instances. |
| Keywords: | SAT problem DPLL complete algorithm decision-making |
| 本文献已被 万方数据 SpringerLink 等数据库收录！ | |