Un cadre général pour l'analyse de conflits - Archive ouverte HAL Access content directly
Conference Papers Year : 2008

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

(1) , (2) , (2) , (1) , (1)
1
2
Lucas Bordeaux
  • Function : Author
  • PersonId : 840367
Youssef Hamadi
  • Function : Author
  • PersonId : 840368
Said Jabbour
Lakhdar Saïs

Abstract

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.
Fichier principal
Vignette du fichier
pages-267-276-article52.pdf (361.05 Ko) Télécharger le fichier
Origin : Files produced by the author(s)
Loading...

Dates and versions

inria-00292660 , version 1 (02-07-2008)

Identifiers

  • HAL Id : inria-00292660 , version 1

Cite

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⟩
50 View
133 Download

Share

Gmail Facebook Twitter LinkedIn More