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.
Type de document :
Communication dans un congrès
Gilles Trombettoni. JFPC 2008- Quatrièmes Journées Francophones de Programmation par Contraintes, Jun 2008, Nantes, France. pp.267-276, 2008
Liste complète des métadonnées

Littérature citée [10 références]  Voir  Masquer  Télécharger

https://hal.inria.fr/inria-00292660
Contributeur : Service Ist Inria Sophia Antipolis-Méditerranée / I3s <>
Soumis le : mercredi 2 juillet 2008 - 11:51:13
Dernière modification le : jeudi 11 janvier 2018 - 06:19:28
Document(s) archivé(s) le : vendredi 28 mai 2010 - 23:04:28

Fichier

pages-267-276-article52.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

  • 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. Gilles Trombettoni. JFPC 2008- Quatrièmes Journées Francophones de Programmation par Contraintes, Jun 2008, Nantes, France. pp.267-276, 2008. 〈inria-00292660〉

Partager

Métriques

Consultations de la notice

126

Téléchargements de fichiers

87