Skip to main navigation Skip to search Skip to main content

Using heuristics to find minimal unsatisfiable subformulas in satisfiability problems

  • Polytechnique Montréal

Research output: Contribution to journal › Journal Article › peer-review

21 Citations (Scopus)

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 languageEnglish
Pages (from-to)124-150
Number of pages27
JournalJournal of Combinatorial Optimization
Volume18
Issue number2
DOIs
Publication statusPublished - Aug 2009
Externally publishedYes

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