Maintaining Soft Arc Consistencies in BnB-ADOPT+ During Search
Proceedings of the Twenty-Third International Joint Conference on Artificial Intelligence. Pages 3227-3227.
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.
@inproceedings{ijcai2013p500,
title = {Maintaining Soft Arc Consistencies in BnB-ADOPT+ During Search},
author = {Lei, Ka Man},
booktitle = {Proceedings of the Twenty-Third International Joint Conference on
Artificial Intelligence, {IJCAI-13}},
publisher = {AAAI Press / International Joint Conferences on Artificial Intelligence},
editor = {Francesca Rossi},
pages = {3227--3227},
year = {2013},
month = {8},
url = {https://ijcai.org/proceedings/2013/500},
}
TY - CPAPER TI - Maintaining Soft Arc Consistencies in BnB-ADOPT+ During Search AU - Lei, Ka Man T2 - Proceedings of the Twenty-Third International Joint Conference on Artificial Intelligence, IJCAI-13 PB - AAAI Press / International Joint Conferences on Artificial Intelligence PY - 2013 SP - 3227 EP - 3227 UR - https://ijcai.org/proceedings/2013/500 ER -Copied
Machine-readable versions of this paper, for tools and AI agents:
