bfSAT: An Incremental SAT Solver Based On Prioritizing Binary Clauses
Lei Gong, Zijian Wang, Chengxiang Chu, Yuping Yuan, Tengfei Wang · 2019 IEEE International Conference on Power, Intelligent Computing and Systems (ICPICS) · 2019
The satisfiability(SAT) problem of large-scale propositional logic formulas has gradually become the mainstream of solutions, and some related algorithms and solvers have emerged. MiniSat is an efficient, open source solver. Its data structure, solution logic and algorithm design are also the basis of current top solvers such as Maple and Glucose. Based on the interpretation of MiniSat, this paper implements the solver bfSAT. bfSAT improves the order of clauses in the process of unit propagation, mainly for prioritizing binary clauses, making it faster to find conflict clauses, get learning clauses and backtrack. bfSAT is a solver based on algorithms and techniques implemented in MiniSat. Therefore, the solver is tested with the SAT competition 2017 benchmark data. Finally, this paper gives some optimization strategies for the world's top solvers.