BnB-ADOPT: an asynchronous branch-and-bound DCOP algorithm
From MaRDI portal
Abstract: 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.
Recommendations
Cited in
(27)- Forward bounding on pseudo-trees for DCOPs and ADCOPs
- Accelerating exact and approximate inference for (distributed) discrete optimization with GPUs
- A distributed optimization method for the geographically distributed data centres problem
- Privacy stochastic games in distributed constraint reasoning
- PC-SyncBB: a privacy preserving collusion secure DCOP algorithm
- Governing convergence of Max-sum on DCOPs through damping and splitting
- Privacy preserving region optimal algorithms for symmetric and asymmetric DCOPs
- Adding laziness in BnB-ADOPT\(^+\)
- Explorative anytime local search for distributed constraint optimization
- Adopt: asynchronous distributed constraint optimization with quality guarantees
- Asymmetric distributed constraint optimization problems
- Connecting BnB-ADOPT with soft arc consistency: initial results
- Distributed Gibbs: a linear-space sampling-based DCOP algorithm
- Removing redundant messages in n-ary BnB-ADOPT
- Asynchronous breadth-first search DCOP algorithm
- Concurrent forward bounding for distributed constraint optimization problems
- Solving distributed constraint optimization problems using logic programming
- scientific article; zbMATH DE number 2087876 (Why is no real title available?)
- Nogood-based asynchronous forward checking algorithms
- Proactive Dynamic Distributed Constraint Optimization Problems
- IDB-ADOPT: A Depth-First Search DCOP Algorithm
- Bounded approximate decentralised coordination via the max-sum algorithm
- Communication-Aware Local Search for Distributed Constraint Optimization
- Distributed Bayesian: A Continuous Distributed Constraint Optimization Problem Solver
- Counterexamples and amendments to the termination and optimality of ADOPT-based algorithms
- Scheduling of Earth observing satellites using distributed constraint optimization
- Probabilistic optimal solution assessment for DCOPs
This page was built for publication: BnB-ADOPT: an asynchronous branch-and-bound DCOP algorithm
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3563097)
