|Títol||Maintaining Soft Arc Consistencies in BnB-ADOPT+ During Search|
|Publication Type||Conference Paper|
|Year of Publication||2013|
|Authors||Gutierrez P, Lee J, Lei KMan, Mak T, Meseguer P|
|Conference Name||19th 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.
- Quant a IIIA