Skip to Main content Skip to Navigation
Conference papers

Un cadre général pour l'analyse de conflits

Résumé : Cet article présente plusieurs contributions au "Conflict Driven Clauses Learning" (CDCL), qui est une des composantes clés des solveurs SAT modernes. Tout d'abord, nous montrons que, à partir du graphe d'implication, les clauses assertives obtenues en utilisant le principe du premier point d'implication unique ("First Unique Implication Point" (FUIP)) sont optimales en terme de saut arrière. Puis nous proposons une extension du graphe d'implication contenant de nouveaux arcs appelés arcs arrières. Ces arcs sont obtenus en tenant compte des clauses satisfaites qui sont habituellement ignorées par l'analyse du conflit. Cette extension capture plus fidèlement l'ensemble du processus de propagation et ouvre de nouvelles perspectives pour les approches fondées sur CDCL. Entre autres avantages, notre extension du graphe d'implication conduit à un nouveau schéma d'analyse des conflits qui exploite les arcs ajoutés et permet des retours arrières plus haut dans l'arbre de recherche. Les résultats expérimentaux montrent que l'intégration de notre système d'analyse des conflits généralisés au sein de solveurs dernier-cri améliore sensiblement leurs performances.
Document type :
Conference papers
Complete list of metadata

Cited literature [10 references]  Display  Hide  Download

https://hal.inria.fr/inria-00292660
Contributor : Service Ist Inria Sophia Antipolis-Méditerranée / I3s <>
Submitted on : Wednesday, July 2, 2008 - 11:51:13 AM
Last modification on : Thursday, September 9, 2021 - 3:10:37 PM
Long-term archiving on: : Friday, May 28, 2010 - 11:04:28 PM

File

pages-267-276-article52.pdf
Files produced by the author(s)

Identifiers

  • HAL Id : inria-00292660, version 1

Collections

Citation

Gilles Audemard, Lucas Bordeaux, Youssef Hamadi, Said Jabbour, Lakhdar Saïs. Un cadre général pour l'analyse de conflits. JFPC 2008- Quatrièmes Journées Francophones de Programmation par Contraintes, LINA - Université de Nantes - Ecole des Mines de Nantes, Jun 2008, Nantes, France. pp.267-276. ⟨inria-00292660⟩

Share

Metrics

Record views

161

Files downloads

167