Skip to Main content Skip to Navigation
Conference papers

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.
Document type :
Conference papers
Complete list of metadata

Cited literature [19 references]  Display  Hide  Download

https://hal.inria.fr/inria-00291560
Contributor : Service Ist Inria Sophia Antipolis-Méditerranée / I3s <>
Submitted on : Friday, June 27, 2008 - 2:30:25 PM
Last modification on : Thursday, March 7, 2019 - 2:52:31 PM
Long-term archiving on: : Friday, May 28, 2010 - 9:05:13 PM

File

pages-165-172-article21.pdf
Files produced by the author(s)

Identifiers

  • HAL Id : inria-00291560, version 1

Collections

Citation

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⟩

Share

Metrics

Record views

1201

Files downloads

1314