Abstract
In this paper, we propose efficient algorithms to extract minimal unsatisfiable subsets of clauses or variables in unsatisfiable propositional formulas. Such subsets yield unsatisfiable propositional subformulas that become satisfiable when any of their clauses or variables is removed. These subformulas have numerous applications, including proving unsatisfiability and post-infeasibility analysis. The algorithms we propose are based on heuristics, and thus, can be applied to large instances. Furthermore, we show that, in some cases, the minimality of the subformulas can be proven with these algorithms. We also present an original algorithm to find minimum cardinality unsatisfiable subformulas in smaller instances. Finally, we report computational experiments on unsatisfiable instances from various sources, that demonstrate the effectiveness of our algorithms.
| Original language | English |
|---|---|
| Pages (from-to) | 124-150 |
| Number of pages | 27 |
| Journal | Journal of Combinatorial Optimization |
| Volume | 18 |
| Issue number | 2 |
| DOIs | |
| Publication status | Published - Aug 2009 |
| Externally published | Yes |
Keywords
- Heuristics
- Minimal unsatisfiable subformulas (MUS)
- Satisfiability
ASJC Scopus subject areas
- Computer Science Applications
- Discrete Mathematics and Combinatorics
- Control and Optimization
- Computational Theory and Mathematics
- Applied Mathematics
Fingerprint
Dive into the research topics of 'Using heuristics to find minimal unsatisfiable subformulas in satisfiability problems'. These topics are generated from the title and abstract of the publication. Together, they form a unique fingerprint.Cite this
- APA
- Author
- BIBTEX
- Harvard
- Standard
- RIS
- Vancouver