[1-11] N-Ary CSPs (N > 2)

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