[This entry reprinted by kind permission of the author: Sunil Mohan <mohan@yoko.rutgers.edu>, Rutgers University] N-ary CSPs have constraints with arbitrary arity, including some with arity > 2. There are some problems with solving CSPs that appear only when encountering constraints with higher arities. Constraints with maximum arity are also called global constraints. Selecting a suitable Variable-Constraint Ordering (Control Sequence) ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ Some of the popular variable ordering heuristics for generating a "good" control sequence fail on N-ary CSPs: - Ordering based on variable domain size. Many such heuristics fail because of their very localized view of the problem. Consider the CSP: {<x1..x5> | T1(x1 x2) T2(x1 x2 x3) T3(x4 x5)} After first selecting (x1 x2 T1), a variable-domain-size based heuristic could proceed to pick x4 as the next variable to bind, when x3 could have been a better choice because it allows T3 to be tested. Or, in Forward-Check, (x1 T1 x2 T3..) is probably a better choice than (x1 T1 x4 T5 x2 T3..), but this heuristic does not have a way of recognizing the presence of higher-arity constraints. This is not a problem with Binary CSPs, particularly in FwdChk, because after binding each variable, a binary constraint on that variable can be tested. - Ordering based on variable connectivity. In a CSP with a global constraint, every variable is connected to n-1 other variables. The same happens with heuristics based on minimizing Constraint Bandwidth [Ramin Zabih, 8th NCAI 1990]. Some Ordering Heuristics for N-ary CSPs ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ I have experimented with the following ordering heuristics: - Minimizing Constraint Bandwidth Sum - Minimizing Constraint Depth Sum (Constr Depth is distance of constr from beginning of sequence) - Ordering variables based on nbr of constraints on it. In general, to generate a good control sequence for N-ary CSPs, a global view of the problem is needed. Binding a variable that allows a (n-ary) constraint that already has the rest of its argument variables bound, should get higher priority than another variable, all other things being equal. Sometimes it is better to view the problem as one of ordering constraints rather than variables. I like to think of testing constraints as early as possible in the search tree. Hence the Constraint BandWidth Sum and Depth Sum heuristics. Of course, variable domain size is also a factor. Decomposing the CSP ~~~~~~~~~~~~~~~~~~~ Freuder [JACM, Jan 1981] showed that tree-shaped CSPs can be solved (find first solution) without backtracking after some consistency processing. Consequently some techniques have been developed to get non-tree problems into that form. Some techniques decompose a CSP into variable clusters such that the shape of the constraint network on these clusters is tree shaped [Dechter & Pearl, AIJ 1989; Gyssens, Jeavons, Cohen, 1992; etc.]. Each variable cluster includes some cluster-local constraints. The complexity of the problem is reduced to the complexity of the largest cluster. With a global constraint in the CSP, this kind of decomposition is not possible. Cycle-cutset based techniques stumble in the same way.Go Back Up