# BnB-ADOPT: An Asynchronous Branch-and-Bound DCOP Algorithm

arXiv: https://arxiv.org/abs/1401.3490 · HTML: https://mlsanity.com/paper/1401.3490/

## Key facts

- Cited by 5 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 15 Jan 2014.

## Built on by (most cited first, 5 of 5)

- [Colosseum: Auditing Collusion in Cooperative Multi-Agent Systems](https://mlsanity.com/paper/2602.15198/) (2026)
- [Pretrained Cost Model for Distributed Constraint Optimization Problems](https://mlsanity.com/paper/2112.04187/) (2021)
- [Latency-Aware 2-Opt Monotonic Local Search for Distributed Constraint Optimization](https://mlsanity.com/paper/2504.08737/) (2025)
- [GDBA Revisited: Unleashing the Power of Guided Local Search for Distributed Constraint Optimization](https://mlsanity.com/paper/2508.06899/) (2025)
- [Symbolic Guidance for LLM Agents in Distributed Multiagent Coordination](https://mlsanity.com/paper/2609.31963/) (2026)

## Abstract (arXiv)

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.