Neighborhood Interchangeability and Dynamic Bundling for Non-Binary Finite CSPs

Anagh Lal, Berthe Y. Choueiry, Eugene C. Freuder

Neighborhood Interchangeability (NI) identifies the equivalent values in the domain of a variable of a Constraint Satisfaction Problem (CSP) by considering only the constraints that directly apply to the variable. Freuder described an algorithm for efficiently computing NI values in binary CSPs. In this paper, we show that the generalization of this algorithm to non-binary CSPs is not straightforward, and introduce an efficient algorithm for computing NI values in the presence of non-binary constraints. Further, we show how to interleave this mechanism with search for solving CSPs, thus yielding a dynamic bundling strategy. While the goal of dynamic bundling is to produce multiple robust solutions, we empirically show that it does not increase (but significantly decreases) the cost of search.

Content Area: 6. Constraint Satisfaction and Satisfiability

Subjects: 15.2 Constraint Satisfaction; 15.7 Search

Submitted: May 10, 2005

This page is copyrighted by AAAI. All rights reserved. Your use of this site constitutes acceptance of all of AAAI's terms and conditions and privacy policy.