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