---
title: "Maintaining Soft Arc Consistencies in BnB-ADOPT+ During Search"
authors:
  - "Ka Man Lei"
doi: ""
url: "https://ijcai.org/proceedings/2013/500"
pdf: "https://ijcai.org/proceedings/2013/0500.pdf"
venue: "Proceedings of the Twenty-Third International Joint Conference on Artificial Intelligence"
year: 2013
pages: "3227-3227"
track: ""
keywords:
---

# Maintaining Soft Arc Consistencies in BnB-ADOPT+ During Search

Ka Man Lei

*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.