Skip to Main content Skip to Navigation
Conference papers

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.
Complete list of metadata

Cited literature [28 references]  Display  Hide  Download

https://hal.inria.fr/inria-00085804
Contributor : Laurent Henocque <>
Submitted on : Friday, July 14, 2006 - 2:48:41 PM
Last modification on : Tuesday, March 16, 2021 - 3:44:16 PM
Long-term archiving on: : Tuesday, April 6, 2010 - 12:09:39 AM

File

Identifiers

  • HAL Id : inria-00085804, version 1
  • PRODINRA : 252446

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, France. ⟨inria-00085804⟩

Share

Metrics

Record views

520

Files downloads

142