local consistency

every solution of the whole problem has to satisfy every part of it

partial solutions for small parts may be easy to find

node consistency

already seen

a variable is node-consistent if every value of its domain satisfies all unary constraints on that variable

formally, if the domain of the variable x is D_x:

∀ a ∈ D_x ∀ C=⟨⟨x⟩,R⟩ . ⟨a⟩ ∈ R

constraint propagation

change the problem so that:

consistency is ensured locally
(for some group of constraints)
solutions of the whole problems are unaffected

These two points are now clarified by an example.

constraint propagation for node consistency

if a variable is not node-consistent,
remove from its domain all values that do not satisfy some unary constraint

D_x' = D_x \ { a | ∃ C . C=⟨⟨x⟩,R⟩ and ⟨a⟩ ∉ R }

does this change satisfy the two conditions?

conditions for constraint satisfaction

consistency ensured locally:: the unary constraints are now satisfied
global solutions unaffected: the removed values were not part of any solution

something similar is now done on binary constraints
then, on groups of constraints

The two conditions are different. The first tells that some group of constraint is now satisfied. Yet, whether these solutions can be extended to the other constraints is not guaranteed. Yet, the second conditions tells that if the original problem has solutions, the modified problems has solutions too.

arc consistency

binary constraints = constraints on two variables

example problem:

variable x with domain {0,1,2,3}
variable y with domain {1,2}
constraint x < y

no unary constraints ⇒ node consistent

any value that can be excluded?

forbidden values

y may only be 1 or 2
x < y
x may only be 0, 1, 2 or 3

x=2 implies that y is larger than 2
x=3 implies that y is larger than 3
but maximal allowed value for y is 2

x=2 and x=3 are not possible
these values are not part of any solution

x can only be 0 or 1

reason

quite obvious
write reason explicitely, so it can be generalized

x=2 is not part of any solution because:

every solution has to satisfy all constraints
therefore, it has to satisfy also x < y
the solution also contain a value for y
if x is 2, the constraint x < y is violated for every possible value of y

conclusion: x=2 is not part of any solution

graphical representation

representation of values
different than the primal graph

nodes:: values of the variables
groups of nodes:: variables
edges:: constraints

solution: value for each variable
satisfy constraints: linked by edges

Precisely, each edge is a tuple in some binary constraint. For example, the edges in the figure represents a binary constraint of scope ⟨x,y⟩ and relation {⟨1,2⟩,⟨0,2⟩,⟨0,1⟩}. The relation is the set of allowed pairs of values for the variables of the scope.

arc consistency, graphically

viewing it from the side of x:

x = 0 is linked to y = 1 and y = 2
x = 1 is linked to y = 2
x = 2 is not linked to anything
x = 3 is not linked to anything

only x = 0 and x = 1 are arc-consistent

constraint propagation

x = 2 is not linked to any value of y
⇒ is not part of any solution

can be removed from the domain of x

same for x = 3

enough?

effect of value removal

other constraints may involve x
example:

originally: z = 2 possible, with x = 3

value x = 3 removed ⇒ z = 2 impossible

again, z may be involved in other constraints…

consistency and propagation

generalizing what done so far:

consistency:: for each every value in the domain of a variable there exists a value in domain of the other so that the pair satisfies a binary constraint
propagation:: the values that do not satisfy this condition can be removed

useful for?…

removed values

does value removal simplify the problem?

2 and 3 removed from the domain of x

example: backtracking
two choices less on x

fewer choices ⇒ simpler to solve

arc consistency, propagation

arc consistency:: when all values in the domain may be part of a solution
(as far as a single constraint is concerned)
propagation:: change che problem to ensure arc consistency
(done by removing the values not satisfying the condition of arc consistency)

arc consistency, formal definition

let C=⟨⟨x,y⟩,R⟩ be a binary constraint

let D_x and D_y be the domains of x and y

variable x is arc-consistent on a binary constraint if for every value a in the domain of x there exists a value b in the domain of y such that the pair a,b satisfieds the constraint

formally:

∀ a ∈ D_x ∃ b ∈ D_y . ⟨a,b⟩ ∈ R

propagation, formal definition

is a change in the domain of x
removal of values not satisfying arc-consistency

D_x' = D_x \ { a | ∀ b ∈ Dy . ⟨a,b⟩ ∉ R }

removal from the domain of x of all values not satisfying arc-consistency with C

empty domain

propagation = removal of values from the domain

may the domain become empty?

yes:

variable x, domain D_x = {2,3}
variable y, domain D_y = {0,1}
constraint x < y

for no value of x there exists a value for y such that they satisfy the constraint

propagation makes D_x empty

empty domain

the domain of even a single variable is empty
⇒ the problem has no solution

why?

every solution includes a value for x
no value for x may satisfy the binary constraint on x

unsatisfiable → empty domain?

empty domain → unsatisfiable

not the converse:

variables x,y,z
domain {0,1} for all three variables
constraints x ≠ y, y ≠ z e z ≠ x

all variables are arc-consistent:
if x = 1 then y = 0 and z = 0
looking only at this variable, this assigment is consistent

the whole problem is inconsistent

arc consistency of a problem

A problem is arc-consistent if every variable and every binary constraint is arc-consistent.

propagation to the whole problem

propagate constraint = restore arc-consistency for a variable and a binary constraint

can be done for the whole problem

  for x in (variables)
    for c in (binary constraints on x)
       restrict domain of x to ensure arc consistency with c

enough?

This algorithm is correct, but it will be shown that more values might be removed that are overlooked by it. In particular, it does not ensure arc-consistency for all variables and constraints.

effects of propagation

  for x in (variables)
    for c in (binary constraints on x)
       restrict domain of x to ensure arc consistency with c

restrict domain of x may make another variable y no longer arc-consistent

effects of propagation: example

every value of z has a corresponding value for x
z is arc consistent

some values of x have no correspondance in y
remove them

effect of value removal

z was arc consistent with x
it no longer is

removal of values 2 and 3 for x
⇒ z=1 and z=2 no longer correspond to values in x

z no longer is arc consistent with x

propagation

z no longer arc consistent
restore consistency by removing values 1 and 2

finished?

final step

x is not arc consistent with z
x=0 do not correspond to any value for z

remove x=0

final situation

propagation restrict the problem to a single solution

problem now trivial: single solution z=0, x=1, y=2

possible outcomes of propagation

a domain becomes empty: the problem has no solution
all domains become singletons: single solution
otherwise: the problem may have solution or not

third case: values removed = fewer possibilities = easier problem

termination

values may be removed, never added

remove value ⇒ re-check consistency of other variables
do not remove ⇒ no need to re-check

at some point, either:

a domain becomes empty ⇒ algorithm done: no solution
no value removed ⇒ algorithm done: arc consistency obtained

the problem with algorithm

  for x in (variables)
    for c in (binary constraints on x)
       restrict domain of x to ensure arc consistency with c

may not obtain arc-consistency

why: x,c only considered once

x may become arc consistent with y
then, values for y are removed
x no longer arc consistent

fix the algorithm

  for x in (variables)
    for c in (binary constraints on x)
       restrict domain of x to ensure arc consistency with c

some variables may be still not arc-consistent

⇒ repeat

how many times?

number of iterations

  for x in (variables)
    for c in (binary constraints on x)
       restrict domain of x to ensure arc consistency with c

some domain changed ⇒ repeat all

maximum number of iterations = one value removed each time

maximum number of iteration = sum of size of domains

Repeating until domains do not change makes the algorithm ensure the arc consistency for all variables and binary constraints. But is not the most efficient way to do that.

propagation: worst case

variable x, domain D_x={0,1,2,3,4}
variable y, domain D_y={0,1,2,3,4}
variable z, domain D_z={0,1,2,3,4}
constraints: x<y, y≤z and z≤x

unsatisfiable

how long does propagation runs?

propagations

variable x, domain D_x={0,1,2,3,4}
variable y, domain D_y={0,1,2,3,4}
variable z, domain D_z={0,1,2,3,4}
constraints: x<y, y≤z and z≤x

one variable at time:

remove 4 from D_x
remove 4 from D_z
remove 4 from D_y
remove 3 from D_x
remove 3 from D_z
remove 3 from D_y
…

but actually…

order of propagation

variable x, domain D_x={0,1,2,3,4}
variable y, domain D_y={0,1,2,3,4}
variable z, domain D_z={0,1,2,3,4}
constraints: x<y, y≤z and z≤x

checking each variable at time
order x,y,z and again

remove 4 from D_x
y is ok
remove 4 from D_z
x is ok
remove 4 from D_y
z is ok
remove 3 from D_x
y is ok
remove 3 from D_z
x is ok
remove 3 from D_y
…

only three variable
same with 100 variables: 2 removals every scan of 100 variables

what to propagate

bad:: check arc-consistency for all variables and constraints
repeat for all variables and constraints until nothing changes
good:: do not check everything each time
keep track of what may be arc inconsistent now

change constraints

for each constraint C=⟨⟨x,y⟩,R⟩:

remove from D_x and D_y all values that are not in the first and second column of R, respectively
remove the rows of R of deleted values
repeat until R no longer changes

ensures the arc consistency of both x and y at the same time

AC-3 algorithm: principle

principle:

ensure the arc consistency on x,y
⇓
remove values from the domain of x and y
⇓
other constraints on x and y may become arc inconsistent

store the list of constraints that may be arc inconsistent
do not check the others

AC-3 algorithm: implementation

stores a set of pairs of variables
these may be arc inconsistent

PossInc={⟨x,y⟩ | ∃ C . C = (⟨x,y⟩,R})
while PossInc ≠ ∅
- select a pair ⟨x,y⟩ ∈ PossInc
- ensure the arc consistency on x,y
- remove the pair: PossInc = PossInc \ {⟨x,y⟩}
- add the pairs that contain either x or y but not both, and are the scope of some constraint:
  PossInc = PossInc ∪ { ⟨z,x⟩ . ∃ C=(⟨z,x⟩,R) } ∪ { ⟨z,y⟩ . ∃ C=(⟨z,y⟩,R) } \ { ⟨x,y⟩ }

omitted: actually, also ⟨x,z⟩ etc.