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.
Type de document :
Communication dans un congrès
Deuxièmes Journées Francophones de Programmation par Contraintes (JFPC06), 2006, Nîmes - Ecole des Mines d'Alès / France, 2006
Liste complète des métadonnées

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

https://hal.inria.fr/inria-00085792
Contributeur : Laurent Henocque <>
Soumis le : vendredi 14 juillet 2006 - 11:10:04
Dernière modification le : jeudi 11 janvier 2018 - 06:19:28
Document(s) archivé(s) le : mardi 6 avril 2010 - 00:09:03

Fichier

Identifiants

  • 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, 2006. 〈inria-00085792〉

Partager

Métriques

Consultations de la notice

186

Téléchargements de fichiers

219