Skip to Main content Skip to Navigation
Conference papers

Extraction de noyaux insatisfiables minimaux de réseaux de contraintes

Résumé : Nous nous intéressons au problème de l'extraction de noyaux insatisfiables minimaux (MUCs) de réseaux de contraintes. Ce problème a un intérêt pratique dans de nombreux domaines d'application tels que la configuration, la planification, le diagnostique, etc. En effet, identifier un ou plusieurs MUCs indépendants, i.e. des MUCs qui ne partagent aucune contrainte, permet d'isoler différentes sources d'inconsistance et de corriger un système incohérent. Dans cet article, nous proposons une approche originale pour extraire un MUC d'un réseau de contraintes. Cette approche comporte deux étapes. La première consiste à exécuter plusieurs fois un algorithme de recherche complète, en utilisant la pondération de contraintes, de manière à circonscrire une partie inconsistante du réseau. La seconde consiste à identifier, en utilisant un processus dichotomique, les contraintes de transition appartenant à un MUC. Nous montrons l'intérêt de cette approche en avançant des arguments théoriques et pratiques.
Complete list of metadata

Cited literature [27 references]  Display  Hide  Download

https://hal.inria.fr/inria-00085792
Contributor : Laurent Henocque <>
Submitted on : Friday, July 14, 2006 - 11:10:04 AM
Last modification on : Thursday, January 11, 2018 - 6:19:28 AM
Long-term archiving on: : Tuesday, April 6, 2010 - 12:09:03 AM

File

Identifiers

  • HAL Id : inria-00085792, version 1

Collections

Citation

Fred Hemery, Christophe Lecoutre, Lakhdar Sais, Frédéric Boussemart. Extraction de noyaux insatisfiables minimaux de réseaux de contraintes. Deuxièmes Journées Francophones de Programmation par Contraintes (JFPC06), 2006, Nîmes - Ecole des Mines d'Alès / France. ⟨inria-00085792⟩

Share

Metrics

Record views

222

Files downloads

267