TitleMaintaining Soft Arc Consistencies in BnB-ADOPT+ During Search
Publication TypeConference Paper
Year of Publication2013
AuthorsGutierrez P, Lee J, Lei KMan, Mak T, Meseguer P
Conference Name19th International Conference on Principles and Practice of Constraint Programming (CP 2013)

Gutierrez and Meseguer show how to enforce consistency in the BnBADOPT+ algorithm for distributed constraint optimization, but they consider unconditional deletions only. 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. We introduce efficient methods to maintain soft arc consistencies in every subproblem during search, a non trivial task because of asynchronicity and induced overheads. Experimental results show substantial benefits on three different benchmarks.