Maintaining Soft Arc Consistencies in BnB-ADOPT+ During Search

Abstract

Gutierrez and Meseguer show how to enforce consistency during distributed search in the BnB-ADOPT+ algorithm for distributed constraint optimization, but they consider only unconditional deletions. However, during search, more values can be pruned conditionally according to variable instantiations that define subproblems. Enforcing consistency in these subproblems can cause further search space reduction. Here we introduce methods to maintain soft arc consistencies in every subproblem during search. Difficulties lie in the asynchronicity of the algorithm and on the overheads induced by backtracking and undoing. After a careful implementation, experimental results show substantial benefits on several benchmarks.