[4K1-GS-1] Fundamental AI, theory: algorithm

[4K1-GS-1-05] Note on CDCL Inference with Similar Learnt Clauses

〇Zhenjiang Zhao¹, Takahisa Toda¹ (1. The University of Electro-Communications)

Keywords:SAT solver, Conflict-driven clause learning

The conflict-driven clause learning (CDCL) is a standard algorithmic framework on which almost state-of-the-art SAT solvers are based. During the solving process of the CDCL solver, many learnt clauses are generated, and those turned out to be useless in terms of some criteria are removed. Since the decision commonly relies on heuristics, the same clauses can appear multiple times. Hence, the evaluation of the learnt clause utility has a significant impact on the solver's performance. The recently proposed DL heuristic determines the utility in terms of the number of times clauses are generated. To improve this, we introduce the similarity of learnt clauses and propose a similarity-based clause management method. In experiments we compared our method with the DL, both implemented on top of CaDiCal, and we confirmed that our method outperforms the DL as well as the intact CaDiCal in both PAR-2 scores and the number of solved instances.