Improving DPOP with branch consistency for solving distributed constraint optimization problems

Ferdinando Fioretto, Tiep Le, William Yeoh, Enrico Pontelli, Tran Cao Son

Research output: Chapter in Book/Report/Conference proceedingConference contribution

18 Scopus citations

Abstract

The DCOP model has gained momentum in recent years thanks to its ability to capture problems that are naturally distributed and cannot be realistically addressed in a centralized manner. Dynamic programming based techniques have been recognized to be among the most effective techniques for building complete DCOP solvers (e.g., DPOP). Unfortunately, they also suffer from a widely recognized drawback: their messages are exponential in size. Another limitation is that most current DCOP algorithms do not actively exploit hard constraints, which are common in many real problems. This paper addresses these two limitations by introducing an algorithm, called BrC-DPOP, that exploits arc consistency and a form of consistency that applies to paths in pseudo-trees to reduce the size of the messages. Experimental results shows that BrC-DPOP uses messages that are up to one order of magnitude smaller than DPOP, and that it can scale up well, being able to solve problems that its counterpart can not.

Original languageEnglish (US)
Title of host publicationPrinciples and Practice of Constraint Programming - 20th International Conference, CP 2014, Proceedings
PublisherSpringer Verlag
Pages307-323
Number of pages17
ISBN (Print)9783319104270
DOIs
StatePublished - 2014
Event20th International Conference on the Principles and Practice of Constraint Programming, CP 2014 - Lyon, France
Duration: Sep 8 2014Sep 12 2014

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume8656 LNCS
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Conference

Conference20th International Conference on the Principles and Practice of Constraint Programming, CP 2014
CountryFrance
CityLyon
Period9/8/149/12/14

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Computer Science(all)

Fingerprint Dive into the research topics of 'Improving DPOP with branch consistency for solving distributed constraint optimization problems'. Together they form a unique fingerprint.

Cite this