TY - GEN
T1 - Improving DPOP with branch consistency for solving distributed constraint optimization problems
AU - Fioretto, Ferdinando
AU - Le, Tiep
AU - Yeoh, William
AU - Pontelli, Enrico
AU - Son, Tran Cao
PY - 2014
Y1 - 2014
N2 - 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.
AB - 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.
UR - http://www.scopus.com/inward/record.url?scp=84906272424&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=84906272424&partnerID=8YFLogxK
U2 - 10.1007/978-3-319-10428-7_24
DO - 10.1007/978-3-319-10428-7_24
M3 - Conference contribution
AN - SCOPUS:84906272424
SN - 9783319104270
T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
SP - 307
EP - 323
BT - Principles and Practice of Constraint Programming - 20th International Conference, CP 2014, Proceedings
PB - Springer Verlag
T2 - 20th International Conference on the Principles and Practice of Constraint Programming, CP 2014
Y2 - 8 September 2014 through 12 September 2014
ER -