Dynamic Branch & Bound Distribué

Résumé : Les méthodes exploitant le principe d'explication [2] (nogoods) pour la résolution des réseaux de contraintes distribués semblent constituer la meilleure approche en termes de complexité théorique en temps. Néanmoins, rares sont les approches d'optimisation qui tirent le meilleur parti de la puissance des nogoods valués [16]. Dans cet article, nous proposons un nouvel algorithme de recherche appliqué aux problèmes d'optimisation de contraintes distribués (DCOPs), appelé Dynamic Branch & Bound Distribué (DisDB&B). Les agents assignent leurs variables d'une manière séquentielle et transmettent en avant leurs nogoods valués. La combinaison des bornes inférieures induites à partir des nogoods valués contribue assurément à l'accélération de la recherche et à l'élimination des sous problèmes irréalisables. Dans cet article, nous montrons que notre algorithme est complet. L'analyse des résultats expérimentaux montrent l'intérêt de notre approche.
Type de document :
Communication dans un congrès
Gilles Trombettoni. JFPC 2008- Quatrièmes Journées Francophones de Programmation par Contraintes, Jun 2008, Nantes, France. pp.165-172, 2008
Liste complète des métadonnées

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

https://hal.inria.fr/inria-00291560
Contributeur : Service Ist Inria Sophia Antipolis-Méditerranée / I3s <>
Soumis le : vendredi 27 juin 2008 - 14:30:25
Dernière modification le : vendredi 11 juillet 2008 - 18:13:09
Document(s) archivé(s) le : vendredi 28 mai 2010 - 21:05:13

Fichier

pages-165-172-article21.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

  • HAL Id : inria-00291560, version 1

Collections

Citation

Imade Benelallam, Mustapha Belaissaoui, Redouane Ezzahir, El Houssine Bouyakhf. Dynamic Branch & Bound Distribué. Gilles Trombettoni. JFPC 2008- Quatrièmes Journées Francophones de Programmation par Contraintes, Jun 2008, Nantes, France. pp.165-172, 2008. 〈inria-00291560〉

Partager

Métriques

Consultations de la notice

668

Téléchargements de fichiers

784