A Generic Approach to Accelerating Belief Propagation based Incomplete Algorithms for DCOPs via A Branch-and-Bound Technique
Belief propagation approaches,such as Max-Sum and its variants,are important methods to solve large-scale Distributed Constraint Optimization Problems(DCOPs).However,for problems with n-ary constraints,these algorithms face a huge challenge since their computational complexity scales exponentially with the number of variables a function holds.In this paper,we present a generic and easy-to-use method based on a branch-and-bound technique to solve the issue,called Function Decomposing and State Pruning(FDSP).We theoretically prove that FDSP can provide monotonically non-increasing upper bounds and speed up belief propagation based incomplete DCOP algorithms without an effect on solution quality.Also,our empirically evaluation indicates that FDSP can reduce 97%of the search space at least and effectively accelerate Max-Sum,compared with the state-of-the-art.
Belief propagation FDSP DCOP
Ziyu Chen Xingqiong Jiang Yanchen Deng Dingding Chen Zhongshi He
College of Computer Science,Chongqing University,Chongqing,China
国内会议
上海
英文
433-451
2019-05-17（万方平台首次上网日期，不代表论文的发表时间）