Abstract:

Distributed constraint optimization problems with finite domains can be solved by asynchronous procedures. ADOPT is the reference algorithm for this kind of problems. Several versions of this algorithm have been proposed, one of them is BnB-ADOPT which changes the nature of the original algorithm from best-first to depth-first search. With BnB-ADOPT, we can assure in some cases that the value of a variable will not be used in the optimal solution. Then, this value can be deleted unconditionally. The contribution of this work consists in propagating these unconditionally deleted values using soft arc consistency techniques, in such a way that they can be known by other variables that share cost functions. When we propagate these unconditional deletions we may generate some new deletions that will also be propagated. The global effect is that we search in a smaller space, causing performance improvements. The effect of the propagation is evaluated on several benchmarks.

• Tagged
• XML
• BibTex