Skip to Main content Skip to Navigation
Conference papers

Approximation d'ensembles horn strong backdoor par recherche locale

Résumé : Dans ce papier, nous proposons une nouvelle approche pour calculer un strong backdoor pour des formules mises sous forme normale conjonctive (CNF). Elle est basée sur une utilisation originale d'une méthode de recherche locale qui fournit un renommage maximisant la sous-formule horn-renommable d'une CNF donnée. Plus précisément, à chaque étape, on choisit de renommer la variable qui fait le plus diminuer le nombre de clauses non-horn. S'il ne reste plus de clauses strictement positives (ou strictement négatives) ou de clauses non-horn dans la formule, notre méthode répond au problème de satisfaisabilité de la formule originale; sinon, on utilise la plus petite sous-formule qui ne soit pas de horn pour en extraire un ensemble de variables (strong backdoor) tel qu'une fois ces variables instanciées, le reste du problème appartient à une classe polynômiale. Les premiers résultats expérimentaux montrent que notre approche est prometteuse sur un grand nombre d'instances SAT.
Complete list of metadata

Cited literature [14 references]  Display  Hide  Download

https://hal.inria.fr/inria-00085807
Contributor : Laurent Henocque <>
Submitted on : Friday, July 14, 2006 - 3:17:42 PM
Last modification on : Monday, March 30, 2020 - 8:53:15 AM
Long-term archiving on: : Tuesday, April 6, 2010 - 12:09:44 AM

File

Identifiers

  • HAL Id : inria-00085807, version 1

Citation

Lionel Paris, Richard Ostrowski, Lakhdar Saïs, Pierre Siegel. Approximation d'ensembles horn strong backdoor par recherche locale. Deuxièmes Journées Francophones de Programmation par Contraintes (JFPC06), 2006, Nîmes - Ecole des Mines d'Alès / France. ⟨inria-00085807⟩

Share

Metrics

Record views

225

Files downloads

436