BnB-ADOPT: an asynchronous branch-and-bound DCOP algorithm
William Yeoh, Ariel Felner, Sven Koenig · 2008
Abstract. Distributed constraint optimization problems (DCOPs) are a popular way of formulating and solving agent-coordination problems. It is often desirable to solve DCOPs optimally with memory-bounded and asynchronous algorithms. We thus introduce Branch-and-Bound ADOPT (BnB-ADOPT), a memory-bounded asynchronous DCOP algorithm that uses the message passing and communication framework of ADOPT, a well known memory-bounded asynchronous DCOP algorithm, but changes the search strategy of ADOPT from best-first search to depth-first branch-and-bound search. Our experimental results show that BnB-ADOPT is up to one order of magnitude faster than ADOPT on a variety of large DCOPs and faster than NCBB, a memory-bounded synchronous DCOP algorithm, on most of these DCOPs. 1