Décomposition arborescente et cohérence locale souple dans les CSP pondérés

Résumé : Plusieurs approches récentes pour résoudre les modèles graphiques (réseaux Bayésiens avec contraintes) exploitent simultanément une décomposition du graphe et le maintien d'une propriété de cohérence locale. La décomposition de graphe exploite la structure du problème, offrant des bornes sur la complexité spatiale et temporelle, tandis que la propagation des contraintes dures conduit en pratique à des améliorations en terme de mémoire et de temps à l'intérieur de ces bornes de complexité théorique. Parallèlement, l'extension des propriétés de cohérence locale au cas des réseaux de contraintes pondérées a permis d'importants gains d'efficacité pour les méthodes fondées sur le principe de séparation et évaluation. En fait, ces cohérences locales souples établissent de manière incrémentale des minorants permettant de couper dans l'arbre de recherche et de guider les heuristiques. Dans cet article, nous considérons la combinaison d'une méthode exploitant la décomposition arborescente avec le maintien d'une propriété de cohérence locale souple pour résoudre des problèmes de satisfaction de contraintes pondérées. L'interaction complexe entre ces deux mécanismes amène à considérer différentes approches ayant différentes propriétés théoriques. Il apparaît que la combinaison la plus prometteuse sacrifie un peu les bornes théoriques pour une meilleure efficacité en pratique.
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 [28 références]  Voir  Masquer  Télécharger

https://hal.inria.fr/inria-00085804
Contributeur : Laurent Henocque <>
Soumis le : vendredi 14 juillet 2006 - 14:48:41
Dernière modification le : mercredi 13 décembre 2017 - 09:02:57
Document(s) archivé(s) le : mardi 6 avril 2010 - 00:09:39

Fichier

Identifiants

  • HAL Id : inria-00085804, version 1

Collections

Citation

Simon De Givry, Thomas Schiex, Gérard Verfaillie. Décomposition arborescente et cohérence locale souple dans les CSP pondérés. Deuxièmes Journées Francophones de Programmation par Contraintes (JFPC06), 2006, Nîmes - Ecole des Mines d'Alès / France, 2006. 〈inria-00085804〉

Partager

Métriques

Consultations de la notice

280

Téléchargements de fichiers

80