TY - JOUR AU - Chen, Ziyu AU - Jiang, Xingqiong AU - Deng, Yanchen AU - Chen, Dingding AU - He, Zhongshi PY - 2019/07/17 Y2 - 2024/03/29 TI - A Generic Approach to Accelerating Belief Propagation Based Incomplete Algorithms for DCOPs via a Branch-and-Bound Technique JF - Proceedings of the AAAI Conference on Artificial Intelligence JA - AAAI VL - 33 IS - 01 SE - AAAI Technical Track: Multiagent Systems DO - 10.1609/aaai.v33i01.33016038 UR - https://ojs.aaai.org/index.php/AAAI/article/view/4559 SP - 6038-6045 AB - <p>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 <em>n</em>-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-touse 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.</p> ER -