BnB-ADOPT: an asynchronous branch-and-bound DCOP algorithm. Yeoh, W., Felner, A., & Koenig, S. Journal of Artificial Intelligence Research, 38:85-133, International Foundation for Autonomous Agents and Multiagent Systems, Richland, SC, 2010.
BnB-ADOPT: an asynchronous branch-and-bound DCOP algorithm [link]Paper  doi  abstract   bibtex   
Distributed constraint optimization (DCOP) problems are a popular way of formulating and solving agent-coordination problems. It is often desirable to solve DCOP problems optimally with memory-bounded and asynchronous algorithms. We 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 DCOP problems and faster than NCBB, a memory-bounded synchronous DCOP algorithm, on most of these DCOP problems.
@article {Yeoh:2008:BAB:1402298.1402307,
	title = {BnB-ADOPT: an asynchronous branch-and-bound DCOP algorithm},
	journal = {Journal of Artificial Intelligence Research},
	volume = {38},
	year = {2010},
	pages = {85-133},
	publisher = {International Foundation for Autonomous Agents and Multiagent Systems},
	address = {Richland, SC},
	abstract = {Distributed constraint optimization (DCOP) problems are a popular way of formulating and solving agent-coordination problems. It is often desirable to solve DCOP problems optimally with memory-bounded and asynchronous algorithms. We 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 DCOP problems and faster than NCBB, a memory-bounded synchronous DCOP algorithm, on most of these DCOP problems.},
	keywords = {agent cooperation, BnB-ADOPT, DCOP, distributed constraint optimization, distributed problem solving},
	issn = {1076-9757},
	doi = {10.1613/jair.2849},
	url = {http://www.jair.org/papers/paper2849.html},
	author = {Yeoh, William and Felner, Ariel and Koenig, Sven}
}

Downloads: 0