• 中国计算机学会会刊
  • 中国科技核心期刊
  • 中文核心期刊

Computer Engineering & Science

Previous Articles     Next Articles

A hybrid learnt clause evaluation algorithm
for SAT problem based on frequency

WU Guan-feng1,2,XU Yang2,3,CHEN Qing-shan1,2,HE Xing-xing2,3,CHANG Wen-jing1,2   

  1. (1.School of Information Science and Technology,Southwest Jiaotong University,Chengdu 610031;
    2.National-Local Joint Engineering Laboratory of System Credibility Automatic Verification,
    Southwest Jiaotong University,Chengdu  610031;
    3.School of Mathematics,Southwest Jiaotong University,Chengdu 610031,China)
  • Received:2018-08-13 Revised:2018-11-08 Online:2019-08-25 Published:2019-08-25

Abstract:

In order to effectively manage learnt clauses, avoid a geometrical growth of their scale, reduce the memory cost of redundant learnt clauses and improve the efficiency of the Boolean satisfiability problem (SAT) solver, we need to evaluate learnt clauses and delete some redundant ones. Traditional evaluation methods are based on the length of learnt clauses, and short-length ones are kept. Two current mainstream clause evaluation methods are the variable state independent decaying sum (VSIDS), and a method based on the evaluation of the literals blocks distance (LBD), and the combination of the above two is also used as the basis for clause evaluation. We analyze the relationship between the number of learnt clauses used in conflict analysis and problem solving, and combine the frequency of learnt clauses with the LBD evaluation algorithm, which not only reflects the role of learnt clauses in conflict analysis, but also makes full use of the information between text and decision-making layer. Taking the Syrup solver (GLUCOSE 4.1 parallel version) as baseline, experiments are carried out to evaluate the algorithm and the parallel clause sharing strategy. The experimental comparison shows that the the proposed hybrid evaluation algorithm outperforms the LBD evaluation algorithm, and the number of solving problems is significantly increased.
 

Key words: SAT problem, parallel solver, LBD, GLUCOSE