Voisinage consistant pour le problème de satisfaisabilité

Lionel Paris 1 Djamal Habet 1 Belaïd Benhamou 1
1 LSIS - Laboratoire des Sciences de l'Information et des Systèmes
Résumé : La plupart des méthodes de recherche locale pour le problème de satisfaisabilité traitent une interprétation complète et souvent inconsistante des variables du problème, et essaient de la réparer en changeant la valeur de vérité de certaines variables jusqu'à atteindre une solution. Nous proposons une nouvelle méthode de recherche locale qui gère des interprétations incomplètes, mais toujours consistantes, au lieu de complètes et inconsistantes. Cette méthode tente de prolonger l'interprétation partielle courante comme le ferait une méthode complète. Cependant, au lieu de déclencher un retour arrière (backtrack) lorsqu'un conflit sur vient, elle libère au moins une variable impliqué dans chaque clause falsifiée a in de restaurer la consistance. Ainsi, le voisinage exploré est toujours consistant alors que ce n'est pas le cas pour les algorithmes de recherche locale classiques. Notre méthode peut aussi tirer profit de certaines techniques efficaces issues des méthodes complètes comme la propagation unitaire et les heuristiques de choix de variables. Les résultats expérimentaux montrent la compétitivité de notre méthode par rapport à d'autres méthodes de recherche locale.
Type de document :
Communication dans un congrès
Troisièmes Journées Francophones de Programmationpar Contraintes (JFPC07), Jun 2007, INRIA, Domaine de Voluceau, Rocquencourt, Yvelines France, 2007, JFPC07
Liste complète des métadonnées

Littérature citée [12 références]  Voir  Masquer  Télécharger
https://hal.inria.fr/inria-00151061
Contributeur : Sylvain Soliman <>
Soumis le : vendredi 1 juin 2007 - 15:15:13
Dernière modification le : jeudi 15 mars 2018 - 16:56:06
Document(s) archivé(s) le : vendredi 21 septembre 2012 - 16:02:13

Fichier

47.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

  • HAL Id : inria-00151061, version 1

Collections

JFPC07 | LSIS | UNIV-AMU | UNIV-TLN | LIS-LAB

Citation

Lionel Paris, Djamal Habet, Belaïd Benhamou. Voisinage consistant pour le problème de satisfaisabilité. Troisièmes Journées Francophones de Programmationpar Contraintes (JFPC07), Jun 2007, INRIA, Domaine de Voluceau, Rocquencourt, Yvelines France, 2007, JFPC07. 〈inria-00151061〉

Exporter

BibTeX TEI DC DCterms EndNote

Partager

Métriques

Consultations de la notice

128

Téléchargements de fichiers

124

Contact


archive-ouverte@inria.fr