Dynamic Branch & Bound Distribué - Inria - Institut national de recherche en sciences et technologies du numérique Accéder directement au contenu
Communication Dans Un Congrès Année : 2008

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.
Fichier principal
Vignette du fichier
pages-165-172-article21.pdf (370.58 Ko) Télécharger le fichier
Origine : Fichiers produits par l'(les) auteur(s)
Loading...

Dates et versions

inria-00291560 , version 1 (27-06-2008)

Identifiants

  • HAL Id : inria-00291560 , version 1

Citer

Imade Benelallam, Mustapha Belaissaoui, Redouane Ezzahir, El Houssine Bouyakhf. Dynamic Branch & Bound Distribué. JFPC 2008- Quatrièmes Journées Francophones de Programmation par Contraintes, LINA - Université de Nantes - Ecole des Mines de Nantes, Jun 2008, Nantes, France. pp.165-172. ⟨inria-00291560⟩

Collections

JFPC08
421 Consultations
489 Téléchargements

Partager

Gmail Facebook X LinkedIn More