Skip to Main content Skip to Navigation
Conference papers

Voisinage consistant pour le problème de satisfaisabilité

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.
Document type :
Conference papers
Complete list of metadata

Cited literature [12 references]  Display  Hide  Download

https://hal.inria.fr/inria-00151061
Contributor : Sylvain Soliman <>
Submitted on : Friday, June 1, 2007 - 3:15:13 PM
Last modification on : Monday, March 30, 2020 - 8:44:53 AM
Long-term archiving on: : Friday, September 21, 2012 - 4:02:13 PM

File

47.pdf
Files produced by the author(s)

Identifiers

  • HAL Id : inria-00151061, version 1

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. ⟨inria-00151061⟩

Share

Metrics

Record views

155

Files downloads

198