Accéder directement au contenu Accéder directement à la navigation
Communication dans un congrès

Algorithme des Poupées Russes exploitant une décomposition arborescente

Résumé : Les problèmes d'optimisation dans les modèles graphiques ont été étudiés dans différents formalismes de l'intelligence artificielle tels que les CSP pondérées (weighted CSP ou WCSP), le maximum de satisfiabilité (MaxSAT) ou dans les réseaux probabilistes (réseaux Bayésiens et champs markoviens). En identifiant des sous-problèmes conditionnellement indépendants,qui sont résolus de façon indépendante et dont l'optimum est mémorisé, il est possible de rendre les algorithmes de type Séparation-évaluation (Branch and Bound) asymptotiquement plus efficaces. Mais la localité des bornes induites par la décomposition affaiblit les effets réels de ce résultat asymptotique car de nombreux sous-problèmes, ne participant pas à la construction d'une solution optimale, sont résolus à l'optimum inutilement. En s'inspirant de l'algorithme des poupées russes (RDS pour Russian Doll Search), une approche possible pour surmonter cette faiblesse consiste à (récursivement) résoudre une relaxation de chacun des sous-problèmes pour obtenir des bornes renforcées. L'algorithme ainsi défini généralise à la fois l'algorithme RDS mais aussi les algorithmes de types Branch and Bound exploitant une décomposition arborescente tels que BTD ou AND-OR Branch and Bound. Nous étudions son efficacité sur différents problèmes et fermons une instance très dure de problème d'affectation de fréquences ouverte depuis plus de 10 ans.
Type de document :
Communication dans un congrès
Liste complète des métadonnées

https://hal.archives-ouvertes.fr/hal-00387845
Déposant : Yves Deville <>
Soumis le : lundi 25 mai 2009 - 23:35:06
Dernière modification le : mercredi 14 octobre 2020 - 04:06:26
Archivage à long terme le : : lundi 15 octobre 2012 - 11:05:08

Fichier

paper_20.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

  • HAL Id : hal-00387845, version 1
  • PRODINRA : 245980

Collections

Citation

M. Sanchez, David Allouche, Simon de Givry, Thomas Schiex. Algorithme des Poupées Russes exploitant une décomposition arborescente. Cinquièmes Journées Francophones de Programmation par Contraintes, Orléans, juin 2009, Jun 2009, France. pp.15-25. ⟨hal-00387845⟩

Partager

Métriques

Consultations de la notice

185

Téléchargements de fichiers

142