Principles of Constraint

Programming
Krzysztof R. Apt

Chapter 5
Local Consistency Notions
 Objectives

• Introduce several local consistency notions:

– node consistency,
– arc consistency,
– hyper-arc consistency,
– directional arc consistency,
– path consistency,
– directional path consistency,
– k-consistency,
– strong k-consistency,
– relational consistency.
• Use the proof theoretic framework to char-
acterize these local consistency notions.

1
 Node Consistency

• CSP is node consistent if for every vari-

able x every unary constraint on x coincides
with the domain of x.
• Examples
Assume C contains no unary constraints.
N – natural numbers,
Z – integers.
– hC, x1 ≥ 0, . . ., xn ≥ 0 ; x1 ∈ N , . . ., xn ∈ N i
is node consistent.
– hC, x1 ≥ 0, . . ., xn ≥ 0 ;
x1 ∈ N , . . ., xn−1 ∈ N , xn ∈ Zi
is not node consistent.

2
 Arc Consistency

• A constraint C on the variables x, y with

the domains X and Y (so C ⊆ X × Y ) is
arc consistent if
– ∀a ∈ X∃b ∈ Y (a, b) ∈ C,
– ∀b ∈ Y ∃a ∈ X (a, b) ∈ C.
• A CSP is arc consistent if all its binary
constraints are.
• Examples
– hx < y ; x ∈ [2..6], y ∈ [3..7]i
is arc consistent.
– hx < y ; x ∈ [2..7], y ∈ [3..7]i
is not arc consistent.

3
 Status of Arc Consistency

• Arc consistency does not imply consistency.

Example Take
hx = y, x 6= y ; x ∈ {a, b}, y ∈ {a, b}i.
• Consistency does not imply arc consistency.

Example Take
hx = y ; x ∈ {a, b}, y ∈ {a}i.
• For some CSP’s arc consistency does imply
consistency.
(A general result later.)

4
 Proof Rules for Arc Consistency

ARC CONSISTENCY 1
hC ; x ∈ Dx, y ∈ Dy i
hC ; x ∈ Dx0 , y ∈ Dy i
where Dx0 := {a ∈ Dx | ∃ b ∈ Dy (a, b) ∈ C}

ARC CONSISTENCY 2
hC ; x ∈ Dx, y ∈ Dy i
hC ; x ∈ Dx, y ∈ Dy0 i
where Dy0 := {b ∈ Dy | ∃ a ∈ Dx (a, b) ∈ C}.

Intuition
Dx0

Dy0 Dy
C

Dx

5
Characterization of Arc Consistency

Note A CSP is arc consistent iff it is closed

under the applications of the ARC CONSIS-
TENCY rules 1 and 2.

6
 Derivation: Example
1 2 3
H O S E S
A T
4 5
H I K E
6 7
A L E E
8
L A S E R
E L

a : C1,2, b : C1,3, c : C4,2, d : C4,5, e : C4,2,

f : C7,2, g : C7,5, h : C8,2, i : C8,6, j : C8,3.

HOSES HOSES a:2

LASER b : 1 a LASER a:2
1 SAILS a : 1 SAILS 2
SHEET a : 1 SHEET e:2
STEER a : 1 STEER e:2
b

c, e
HEEL c:1 HOSES b:2
HIKE LASER b:2
4 KEEL c:1 SAILS j:2 3
KNOT c:1 d SHEET j:2
LINE d:1 STEER
f

AFT f :1 HEEL d:2

ALE f :1 g HIKE d:2
7 EEL f :1 KEEL 5
LEE KNOT g:2
TIE f :1 j LINE d:2
h

HOSES i:1 i AFT i:2

LASER ALE
8 SAILS h:1 EEL i:2 6
SHEET h:1 LEE i:2
STEER h:1 TIE i:2

7
 Hyper-arc Consistency

• A constraint C on the variables x1, . . ., xn

with the domains D1, . . ., Dn is hyper-arc
consistent if
∀i ∈ [1..n]∀a ∈ Di ∃d ∈ C a = d[xi].
• CSP is hyper-arc consistent if all its
constraints are.
• Examples
– hx ∧ y = z ; x = 1, y ∈ {0, 1}, z ∈ {0, 1}i
is hyper-arc consistent.
– hx ∧ y = z ; x ∈ {0, 1}, y ∈ {0, 1}, z = 1i
is not hyper-arc consistent.

8
 Characterization of
Hyper-arc Consistency

HYPER-ARC CONSISTENCY
hC ; x1 ∈ D1, . . ., xn ∈ Dni
hC ; . . ., xi ∈ Di0 , . . .i
C a constraint on the variables x1, . . ., xn,
i ∈ [1..n],
Di0 := {a ∈ Di | ∃d ∈ C a = d[xi]}.

Note A CSP is hyper-arc consistent iff it is

closed under the applications of the HYPER-
ARC CONSISTENCY rule.

9
 Directional Arc Consistency

Assume a linear ordering ≺ on the variables.

• A constraint C on x, y with the domains Dx
and Dy is directionally arc consistent
w.r.t. ≺ if
– ∀a ∈ Dx∃b ∈ Dy (a, b) ∈ C
provided x ≺ y,
– ∀b ∈ Dy ∃a ∈ Dx (a, b) ∈ C
provided y ≺ x.
• A CSP is directionally arc consistent
w.r.t. ≺ if all its binary constraints are.

Example
hx < y ; x ∈ [2..7], y ∈ [3..7]i
is
• not arc consistent,
• directionally arc consistent w.r.t. y ≺ x.
• not directionally arc consistent w.r.t.
x ≺ y.
10
 Characterization of
Directional Arc Consistency

Define P≺:
P with the variables reordered w.r.t. ≺.
Example
Take P :=
hx < y, y 6= z ; x ∈ [2..10], y ∈ [3..7], z ∈ [3..6]i
and
y ≺ x ≺ z.
Then P≺ :=
hy > x, y 6= z ; y ∈ [3..7], x ∈ [2..10], z ∈ [3..6]i.

Note A CSP P is directionally arc consis-

tent w.r.t. ≺ iff the CSP P≺ is closed un-
der the applications of the ARC CONSIS-
TENCY rule 1.

11
 Limitations of Arc Consistency

Note
hx < y, y < z, z < x ; x, y, z ∈ {1..100000}i.
is inconsistent.
Proof using arc consistency rules.
Applying ARC CONSISTENCY rule 1 we
get
hx < y, y < z, z < x ; x ∈ {1..99999}, y, z ∈ {1..100000}i,
etc.
Disadvantages:
• Large number of steps.
• Length depends on the size of the domains.

Direct proof: use transitivity of <.

Path consistency: a generalizes this form
of reasoning to arbitrary binary relations.

12
 Normalized CSP’s

A CSP P is normalized if for each pair x, y

of its variables at most one constraint on x, y
exists.
Denote by Cx,y the unique constraint on x, y
if it exists and otherwise the “universal” rela-
tion on x, y.
R and S: two binary relations.
• transposition of R:
RT := {(b, a) | (a, b) ∈ R},
• composition of R and S by
R·S := {(a, b) | ∃c ((a, c) ∈ R, (c, b) ∈ S)}.

13
 Path Consistency

A normalized CSP is path consistent if for

each subset {x, y, z} of its variables
Cx,z ⊆ Cx,y · Cy,z .

Note A normalized CSP is path consistent iff

for each subsequence x, y, z of its variables
T ,
Cx,y ⊆ Cx,z · Cy,z

Cx,z ⊆ Cx,y · Cy,z ,

T ·C .
Cy,z ⊆ Cx,y x,z

Intuition
y

Cx,y Cy,z

x Cx,z z

14
 Path Consistency: Example 1

hx < y, y < z, x < z;

x ∈ [0..4], y ∈ [1..5], z ∈ [6..10]i
z [6..10]

< >

<

x [0..4] y [1..5]

is path consistent. Indeed

Cx,y = {(a, b) | a < b, a ∈ [0..4], b ∈ [1..5]},

Cx,z = {(a, c) | a < c, a ∈ [0..4], c ∈ [6..10]},

Cy,z = {(b, c) | b < c, b ∈ [1..5], c ∈ [6..10]},

and all 3 conditions are satisfied.

15
 Path Consistency: Example 2

hx < y, y < z, x < z;

x ∈ [0..4], y ∈ [1..5], z ∈ [5..10]i
z [5..10]

< <

<

x [0..4] y [1..5]

is not path consistent. Indeed, now

Cx,z = {(a, c) | a < c, a ∈ [0..4], c ∈ [5..10]}
and for 4 ∈ [0..4] and 5 ∈ [5..10] no b ∈ [1..5]
exists such that 4 < b and b < 5.

16
Characterization of Path Consistency

PATH CONSISTENCY 1
Cx,y , Cx,z , Cy,z
0 ,C ,C
Cx,y x,z y,z
0 := C T
where Cx,y x,y ∩ Cx,z · Cy,z ,

PATH CONSISTENCY 2
Cx,y , Cx,z , Cy,z
0 ,C
Cx,y , Cx,z y,z
0 := C
where Cx,z x,z ∩ Cx,y · Cy,z ,

PATH CONSISTENCY 3
Cx,y , Cx,z , Cy,z
0
Cx,y , Cx,z , Cy,z
0 := C T
where Cy,z y,z ∩ Cx,y · Cx,z .
Note A normalized CSP is path consistent iff
it is closed under the applications of the PATH
CONSISTENCY rules 1, 2 and 3.
17
 m-Path Consistency

A normalized CSP is m-path consistent

(m ≥ 2) if for each subset {x1, . . ., xm+1} of
its variables
Cx1,xm+1 ⊆ Cx1,x2 · Cx2,x3 · ... · Cxm,xm+1 .

Note A normalized CSP is m-path consistent

if for each subset {x1, . . ., xm+1} of its vari-
ables
if (a1, am+1) ∈ Cx1,xm+1 , then for some
a2, . . ., am for all i ∈ [1..m]
(ai, ai+1) ∈ Cxi,xi+1 .
a2, . . ., am: path connecting a1 and am+1.
Theorem Every normalized path consistent
CSP is m-path consistent for each m ≥ 2.
Proof. Induction on m.

18
 Directional Path Consistency

Assume a linear ordering ≺ on the variables. A

normalized CSP is directionally path con-
sistent w.r.t. ≺ if for each subset {x, y, z}
of its variables
Cx,z ⊆ Cx,y · Cy,z provided x, z ≺ y.

Note A normalized CSP is directionally path

consistent w.r.t. ≺ iff for each subsequence
x, y, z of its variables
T provided x, y ≺ z,
Cx,y ⊆ Cx,z · Cy,z

Cx,z ⊆ Cx,y · Cy,z provided x, z ≺ y,

T ·C
Cy,z ⊆ Cx,y x,z provided y, z ≺ x.

19
 Examples

Reconsider
hx < y, y < z, x < z;
x ∈ [0..4], y ∈ [1..5], z ∈ [5..10]i
Then
Cx,y = {(a, b) | a < b, a ∈ [0..4], b ∈ [1..5]},

Cx,z = {(a, c) | a < c, a ∈ [0..4], c ∈ [5..10]},

Cy,z = {(b, c) | b < c, b ∈ [1..5], c ∈ [5..10]}.

• It is directionally path consistent w.r.t. the

ordering ≺ in which x, y ≺ z.
Indeed, for every pair (a, b) ∈ Cx,y there
exists c ∈ [5..10] such that a < c and b < c.
• It is directionally path consistent w.r.t. the
ordering ≺ in which y, z ≺ x.
Indeed, for every pair (b, c) ∈ Cy,z there
exists a ∈ [0..4] such that a < b and a < c.
20
 Characterization of
Directional Path Consistency

Note A normalized CSP P is directionally

path consistent w.r.t. ≺ iff P≺ is closed un-
der the applications of the PATH CONSIS-
TENCY rule 1.

21
 Instantiations

Fix a CSP P.
• Instantiation: function on a subset of the
variables of P. It assigns to each variable a
value from its domain.
Notation:
{(x1, d1), . . ., (xk , dk )}.
• C: a constraint on x1, . . ., xk .
Instantiation {(x1, d1), . . ., (xk , dk )}
satisfies C if (d1, . . ., dk ) ∈ C.
• I: instantiation with a domain X, Y ⊆ X.
I | Y : restriction of I to Y .
• Instantiation I with domain X is consis-
tent if for every constraint C of P on some
Y with Y ⊆ X I | Y satisfies C.
• Consistent instantiation is k-consistent if
its domain consists of k variables.
• An instantiation is a solution to P if it is
consistent and defined on all variables of P.
22
 Example

Consider
hx < y, y < z, x < z ; x ∈ [0..4], y ∈ [1..5], z ∈ [5..10]i.
Let I := {(x, 0), (y, 5), (z, 6)}.
z [5..10]

< <

<

x [0..4] y [1..5]

• I | {x, y} = {(x, 0), (y, 5)}.

It satisfies x < y.
• I | {x, z} = {(x, 0), (z, 6)}.
It satisfies x < z.
• I | {y, z} = {(y, 5), (z, 6)}.
It satisfies y < z.
• So I is a 3-consistent instantiation. It is a
solution to this CSP.

23
 k-Consistency

• CSP is 1-consistent if for every variable x

with a domain D each unary constraint on
x equals D.
• CSP is k-consistent, k > 1, if every (k −
1)-consistent instantiation can be extended
to a k-consistent instantiation no matter
which new variable is chosen.
k-consistency aka node consistency
Note
• A node consistent CSP is arc consistent iff
it is 2-consistent.
• A node consistent normalized binary CSP
is path consistent iff it is 3-consistent.

24
 k-Consistency, ctd

Fix k > 1.
(i) There exists a CSP that is (k−1)-consistent
but not k-consistent.
(ii) There exists a CSP that is not (k − 1)-
consistent but is k-consistent.
Proof of (i) for k = 3:
x3 [0..1]

6= 6=

6=

x1 [0..1] x2 [0..1]

Proof of (ii):
• x1 {a, b}

6=
6=
• x2 {a}

• x3 {a}

...

• xk {a}

25
 Strong k-Consistency

CSP strongly k-consistent, k ≥ 1, if it is

i-consistent for every i ∈ [1..k].
Theorem Take a CSP with k variables,
k ≥ 1, such that
• at least one domain is non-empty,
• it is strongly k-consistent.
Then it is consistent.
Proof. Construct a solution by induction.
Prove that
(i) there exists a 1-consistent instantiation,
(ii) for every i ∈ [2..k] each (i−1)-consistent in-
stantiation can be extended to an i-consistent
instantiation.

Disadvantage Required level of strong con-

sistency = # of variables.

26
 Graphs and CSP’s

Graph is associated with a CSP P.

Nodes: variables of P.
Arcs: connect two variables if they appear
jointly in some constraint.

27
 Examples

• SEND + MORE = MONEY puzzle.

The graph has 8 nodes, S, E, N, D, M, O, R, Y ,
and is complete.

• hx + y = z, x + u = v ; DEi
x
y

u
z

• hx < z, x < y, y < u, y < v ; DEi

x y

z
u
v

28
 Width of a Graph

G: a finite graph G.
≺: linear ordering on the nodes of G.
• ≺-width of a node of G: number of arcs
in G that connect it to ≺-smaller nodes.
• ≺-width of G: maximum of the ≺-widths
of its nodes.
• The width of G: minimum of ≺-widths for
all linear orderings ≺.

Examples
• SEND + MORE = MONEY puzzle.
Complete graph with 8 nodes, so its width
= 7.
x y

z
u
v

• It is a tree, so its width = 1.

29
 Examples, ctd
x
y

u
z

x y z v u
≺-width: 0 1 2 1 2

u v z y x
≺-width: 0 1 0 1 4

Two examples of the ≺-widths of the nodes

Here width = 2.

30
Consistency via Strong k-Consistency

Theorem Given: a CSP such that

• all domains are non-empty,
• it is strongly k-consistent,
• the graph associated with it has width k−1.
Then this CSP is consistent.
Proof. (Sketch)
Assume n variables.
• Reorder the variables so that the resulting
≺-width is k − 1.
• Prove by induction that
– there exists consistent instantiation with
domain {x1},
– for every j ∈ [1..n − 1] each consistent in-
stantiation with domain {x1, . . ., xj } can
be extended to a consistent instantiation
with domain {x1, . . ., xj+1}.

31
 Useful Corollaries
Corollary 1
Given: P and a linear ordering ≺ such that
• all domains are non-empty,
• P is
– node consistent,
– directionally arc consistent w.r.t. ≺,
• the ≺-width of the graph associated with P
is 1.
Then P is consistent.
Corollary 2
Given: P and a linear ordering ≺ such that
• all domains are non-empty,
• P is
– directionally arc consistent w.r.t. ≺,
– directionally path consistent w.r.t. ≺,
• the ≺-width of the graph associated with it
is 2.
Then P is consistent.
32
 Relational Consistency

“Ultimate” notion of local consistency

• Given: P and a subsequence C of its con-

straints.
P | C:
– remove from P all constraints not in C,
– delete all domain expressions involving vari-
ables not present in any constraint in C.
• P is relationally (i, m)-consistent if for
every sequence C of m constraints and X ⊆ Var (C)
of size i:
every consistent instantiation with the do-
main X can be extended to a solution to
P | C.

33
 Relational Consistency, ctd

Intuition:
For every sequence of m constraints and for
every set X of i variables, each present in one
of these m constraints:
each consistent instantiation with the do-
main X can be extended to a solution to
all these m constraints.

Some properties
• A node consistent binary CSP is arc consis-
tent iff it is relationally (1, 1)-consistent.
• A node consistent CSP is hyper-arc consis-
tent iff it is relationally (1, 1)-consistent.
• Every node consistent normalized relation-
ally (2, 3)-consistent CSP is path consistent.
• Every strictly binary relationally (k − 1, k)-
consistent CSP is k-consistent.
• A CSP with m constraints is consistent iff
it is relationally (0, m)-consistent.
34
 Some Notation

• Given: constraint C on variables X, sub-

sequence Y of X.
ΠY (C) := {d[Y ] | d ∈ C}.
• X: sequence of variables,
X1, . . ., Xn: subsequences of X.
union of X1, . . ., Xn: shortest subsequence
of X containing each Xi as a subsequence.
Example: Take x1, x2, x4, x5.
Union of (x2, x4), (x4, x5), (x2, x5) is x2, x4, x5.
• Given: a sequence of constraints C1, . . ., Cm
on variables X1, . . ., Xm.
C1 1 . . . 1 Cm := {d | d[Xi] ∈ Ci for i ∈ [1..m]}.
C1 1 . . . 1 Cm is a constraint on the
“union” of X1, . . ., Xm.
• X: a sequence of variables
CX :=1 {CY | Y is a subsequence of X}.

35
 Characterization of k-Consistency

Note d is a solution to hC1, . . ., Cm ; DEi iff

d ∈ C1 1 . . . 1 C m .
A CSP P regular if for each sequence X of
its variables a unique constraint on X exists.
Denote it by CX .

k-CONSISTENCY
CX
CX ∩ ΠX (CX,y )

Note If a regular CSP is closed under the ap-

plications of the k-CONSISTENCY rule for
all subsequences X of k − 1 variables and all
variables y not in X, then it is k-consistent.

36
Characterization of Relational Consistency

RELATIONAL (i, m)-CONSISTENCY

CX
CX ∩ ΠX (C1 1 . . . 1 Cm)

Note If a regular CSP is closed under the ap-

plications of
RELATIONAL (i, m)-CONSISTENCY
rule for each subsequence of constraints C1, . . ., Cm
and each subsequence X of Var (C1, . . ., Cm)
of length i, then it is relationally (i, m)-consistent.

37
 Objectives

• Introduce several local consistency notions:

– node consistency,
– arc consistency,
– hyper-arc consistency,
– directional arc consistency,
– path consistency,
– directional path consistency,
– k-consistency,
– strong k-consistency,
– relational consistency.
• Use the proof theoretic framework to char-
acterize these local consistency notions.

38