BnB-ADOPT: An Asynchronous Branch-and-Bound DCOP Algorithm
  Distributed constraint optimization (DCOP) problems are a popular way of
formulating and solving agent-coordination problems. A DCOP problem is a
problem where several agents coordinate their values such that the sum of the
resulting constraint costs is minimal. It is often desirable to solve DCOP
problems with memory-bounded and asynchronous algorithms. We introduce
Branch-and-Bound ADOPT (BnB-ADOPT), a memory-bounded asynchronous DCOP search
algorithm that uses the message-passing and communication framework of ADOPT
(Modi, Shen, Tambe, and Yokoo, 2005), a well known memory-bounded asynchronous
DCOP search 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 finds cost-minimal solutions up to one order of magnitude faster
than ADOPT for a variety of large DCOP problems and is as fast as NCBB, a
memory-bounded synchronous DCOP search algorithm, for most of these DCOP
problems. Additionally, it is often desirable to find bounded-error solutions
for DCOP problems within a reasonable amount of time since finding cost-minimal
solutions is NP-hard. The existing bounded-error approximation mechanism allows
users only to specify an absolute error bound on the solution cost but a
relative error bound is often more intuitive. Thus, we present two new
bounded-error approximation mechanisms that allow for relative error bounds and
implement them on top of BnB-ADOPT.
