Approximating minimal unsatisfiable subformulae by means of adaptive core search

详细信息    查看全文

• 作者：Bruni ; Renato
• 关键词：Consistency restoring ; Enumeration ; (Un)Satisfiability
• 刊名：Discrete Applied Mathematics
• 出版年：2003
• 出版时间：August 15, 2003
• 年：2003
• 卷：130
• 期：2
• 页码：85-100
• 全文大小：246 K

文摘

The paper is concerned with the relevant practical problem of selecting a small unsatisfiable subset of clauses inside an unsatisfiable CNF formula. Moreover, it deals with the algorithmic problem of improving an enumerative (DPLL-style) approach to SAT, in order to overcome some structural defects of such an approach. Within a complete solution framework, we are able to evaluate the difficulty of each clause by analyzing the history of the search. Such clause hardness evaluation is used in order to rapidly select an unsatisfiable subformula (of the given CNF) which is a good approximation of a minimal unsatisfiable subformula (MUS). Unsatisfiability is proved by solving only such subformula. Very small unsatisfiable subformulae are detected inside famous Dimacs unsatisfiable problems and in real-world problems. Comparison with the very efficient solver SATO 3.2 used as a state-of-the-art DPLL procedure (disabling learning of new clauses) shows the effectiveness of such enumeration guide.