BnB-ADOPT
Patricia Gutierrez, Pedro Meseguer · Frontiers in artificial intelligence and applications · 2010
Distributed constraint optimization problems can be solved by BnB-ADOPT+, a distributed asynchronous search algorithm. In the centralized case, local consistency techniques applied to constraint optimization have been shown very beneficial to increase performance. In this paper, we combine BnB-ADOPT+with different levels of soft arc consistency, propagating unconditional deletions caused by either the enforced local consistency or by distributed search. The new algorithm maintains BnB-ADOPT+optimality and termination. In practice, this approach decreases substantially BnB-ADOPT+requirements in communication cost and computation effort when solving commonly used benchmarks.