DIGITAL.CSIC. Repositorio Institucional del CSIC
Publicación
Contribución de congreso (ConferenceOutput)
An Effective Learnt Clause Minimization Approach for CDCL SAT Solvers
Learnt clauses in CDCL SAT solvers often contain redundant literals. This may have a negative impact on performance because redundant literals may deteriorate both the effectiveness of Boolean constraint propagation and the quality of subsequent learnt clauses. To overcome this drawback, we define a new inprocessing SAT approach which eliminates redundant literals from learnt clauses by applying Boolean constraint propagation. Learnt clause minimization is activated before the SAT solver triggers some selected restarts, and affects only some learnt clauses during the search process. Moreover, we conducted an empirical evaluation on instances coming from the hard combinatorial and application categories of recent SAT competitions. The results show that a remarkable number of additional instances are solved when the approach is incorporated into five of the best performing CDCL SAT solvers. Copyright © 2018, IJCAI, Research partially supported by the National Natural Science Foundation of China (Grants no. 61370183, 61370184, 61472147), the Generalitat de Catalunya grant AGAUR 2014-SGR-118, and the MINECO-FEDER project RASO TIN2015-71799-C2-1-P., Peer Reviewed