CSE 990
Advanced Constraint Processing
y
Notes on the last 15 minutes of the discussion on January 23, 2003.
Recorded by Eric Moss.
====================================================================

After much clarification, it was determined that Dechter's definition 3.4.1
of i-consistency is the same as that presented for k-consistency in the
421-821 course.

The plain English summary of Definition 3.4.1, page 77, for a given
relation and a given variable not included in that relation, is as follows:

Given the variables {Vj} in a CSP, start with a subset of them called S.
Assume it is of size i - 1 (for the sake of the definition).  

Take any tuple of values, chosen one from each variable in S and call that
tuple t.  A set of such tuples is denoted {t}.

Now, all of the constraint arcs in the subset S will, taken together,
select from all possible tuples -- |D|^|S| of them if each domain is of
size |D| -- those that satisfy all the constraints in S simultaneously. 

Denote that set of all allowed tuples from S by the relation Rs.

Remember, we assumed that the size of S is i-1.

Now, pick a variable y NOT in S, that is, an i'th variable.

We say the relation Rs is "i-consistent" relative to y if and only if we
can pick any tuple t in the relation Rs, and find some value in the domain
of y that will satisfy all the constraints connecting all i variables. 

In other words:

Given a relation Rs among i-1 variables listing all allowed tuples of size
i-1 taken from those variables, that relation is "i-constistent for a
particular y not in that set" iff every tuple t in Rs can be extended to a
consistent tuple by including SOME element from the domain of y.

This definition applies only to a given S, that S's relation Rs and a
particular variable y not in S.

If all tuples in Rs that cannot be extended to include variable y (that is,
those that have no support in y) are removed, and there is at least one
tuple remaining, the new relation Rs' will be i-consistent.


I-CONSISTENCY AS APPLIED TO NETWORKS, NOT JUST PARTICULAR RELATIONS AND
VARIABLES: 

NOW we extend this definition to apply to a network.  We say a network is
"i-consistent" iff all possible subsets of size i-1 can be extended by each
of the remaining variables.  That is, iff you can do all of the following:

[1] Pick ANY i-1 variables from it.  Call that subset S.  There will be
nC(i-1) such subsets you must check.
[2] Find a non-empty set of tuples t among those variables that satisfy all
    the constraints connecting those variables.  Denote that set by the
    relation Rs = {t}.
[3] Pick ANY tuple t from that set (Rs).
[4] Pick ANY other variable y not in S AND
[5] Find in y's domain some value that, added to the tuple t forms a tuple
    of size i that satisfies all constraints connecting the union S U y.

In summary, "i-consisent" can be applied to:

[1] a particular relation of arity i-1 with respect to a particular
    variable not in that relation.
[2] a network, by requiring i-consistency of ALL possible combinations of
    i-1 sized subsets S of variables (and the relations Rs describing the
    allowed tuples of S) that you can choose from that network. 

STRONG i-consistency refers to a network which is j-consistent for j <= i.
That is, you can pick all variable subsets of size 1, and for each of them,
verify that its tuples (of size 1) are consistent (i.e., node consistency).
Then you can show that for any other variable, at least one of that
variable's values forms a valid tuple (size 2) with the original tuple.
(This is just arc-consistency.)  Then you can pick all variable subsets of
size 2 and for each subset, you can pick ANY other variable and one of its
values will extend the partial solution of size 2 to one of size 3 (path
consistency in binary networks), and so on up to extending tuples of size
i-1 to tuples of size i. 

Achieving strong n-consistency means you have all tuples that solve the
original problem.


========================================

The next point was to notice that the revise-i algorithm on page 78 is the
generalization of the Revise algorithm we learned in 421/821 for enforcing
arc-consistency (i.e., 2-consistency).  The algorithm assumes we are
extensionally defining the relations between variables, i.e. by enumerating
all allowed tuples.  It just says that given a set S of i-1 variables, a
relation on S enumerating all allowed tuples, an i'th variable y, and the
constraints joining that variable to the subgraph S, we will remove all
tuples from Rs that have no support from the i'th variable.  That is, we
remove from Rs all its tuples that can't be extended to solutions for the
subgraph S U y.

This has the same effect as the algorithm described by Freuder for
propagating the reductions of a relation (in his paper on synthesizing
constraints).  That is, when we are merging i-1 arity relations to form an
i-arity relation, we remove from the relation being added to any of its
tuples that can't be extended into the new, larger relation.


========================================

Finally, we noted on pages 80 and 81 that generalized arc-consistency
updates the domain of a variable x by:

[1] treating the domain of x ("Dx") as a unary constraint relation.
[2] picking the set S of variables to which x is being related.
[3] enumerating allowed tuples from the set S and calling that set Rs.
[4] joining Rs to Dx to pick up values in Dx that are consistent
    with the tuples in Rs
[5] projecting that join onto the variable x
[6] removing values in x not in that projection.

That makes sense because generalized arc consistency is defined for a
variable relative to a relation (as opposed to a relation relative to a
variable as with i-consistency), and requires that every value of a
variable x be found in some tuple of Rs where Rs describes allowable tuples
of S.  

This is a bit weird since Definition 3.5.1 (p. 80) doesn't specify if x is
in S or not.  That would make a difference, I'd think.


RELATIONAL arc-consistency still confuses me.  It appears to modify not the
domain of some variable x, but a relation Rs-, which is a relation
describing all legal tuples for the set S - x.  It does so by removing from
the relation over all variables EXCEPT x any tuples that aren't extended in
the join of Rs and Dx.

I haven't figured out what this corresponds to in Freuder's paper, if
anything.  It seemed a likely thing to ask, since all the other algorithms
in this chapter of Dechter's book related to Freuder.