Passer à la navigation principale Passer à la recherche Passer au contenu principal

Using heuristics to find minimal unsatisfiable subformulas in satisfiability problems

  • Polytechnique Montréal

Résultats de recherche: Contribution à un journal › Article publié dans une revue, révisé par les pairs › Revue par des pairs

21 Citations (Scopus)

Résumé

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.

Langue originaleAnglais
Pages (de - à)124-150
Nombre de pages27
RevueJournal of Combinatorial Optimization
Volume18
Numéro de publication2
Les DOIs
ÉtatPublié - août 2009
Modification externeOui

Classification disciplinaire ASJC Scopus

  • Applications de l'informatique
  • Mathématiques discrètes et combinatoires
  • Contrôle et optimisation
  • Mathématiques et théorie de l'informatique
  • Mathématiques appliquées

Empreinte digitale

Voici les principaux termes ou expressions associés à « Using heuristics to find minimal unsatisfiable subformulas in satisfiability problems ». Ces libellés thématiques sont générés à partir du titre et du résumé de la publication. Ensemble, ils forment une empreinte digitale unique.

Citer cette ressource