Constraint Programming

– Searching : Part 1 –

Christophe Lecoutre
lecoutre@[Link]

CRIL-CNRS UMR 8188

Universite d’Artois
Lens, France

January 2025

1
Outline

1 Backtracking Search

2 Search Ordering Heuristics

3 Guiding Search toward Conflicts

2
Search Space

For a given CN P such that:

• n is the number of variables
• d is the greatest domain size
• e is the number of constraints
• r is the greatest constraint arity

What is the complexity of a Generate and Test approach?

Answer: O(d n er ), assuming that a constraint check is O(r )

3
Search Space

For a given CN P such that:

• n is the number of variables
• d is the greatest domain size
• e is the number of constraints
• r is the greatest constraint arity

What is the complexity of a Generate and Test approach?

Answer: O(d n er ), assuming that a constraint check is O(r )

3
Search Space

For a given CN P such that:

• n is the number of variables
• d is the greatest domain size
• e is the number of constraints
• r is the greatest constraint arity

What is the complexity of a Generate and Test approach?

Answer: O(d n er ), assuming that a constraint check is O(r )

3
Exponential Growth

Suppose that:
• the complexity is only O(2n )
• 109 complete instantiations can be processed any new second

n 2n Processing Time
10 around 103 around 1 nanosecond
20 around 106 around 1 millisecond
30 around 109 around 1 second
40 around 1012 around 16 minutes
50 around 1015 around 11 days
60 around 1018 around 32 years
70 around 1021 around 317 centuries

4
Search Tree
Most of the time, the search space can be perceived as a search tree.

5
Pruning the Search Tree

Constraint Inference (Filtering/Propagation) can help us!

6
Pruning the Search Tree
Finding a solution may become realistic in a reduced search tree.

7
Constraint Inference Only?

Solving a CN by only employing constraint propagation is very rare. To

find a solution, one has then to explore the search tree with:
• either a complete method: full exploration of the search space
• or an incomplete method: partial exploration of the search space

In any case, it may look like searching a needle in a haystack!

8
Complete Exploration

Classical approach
• depth-first traversal
• backtracking mecanism
• interleaving of
• decisions
• propagations

Remark.
Other strategies exist:
• breadth-first traversal
• limited discrepancy search (LDS)
• large neighborhood search (LNS)
• ...

9
Complete Exploration

Classical approach
• depth-first traversal
• backtracking mecanism
• interleaving of
• decisions
• propagations

Remark.
Other strategies exist:
• breadth-first traversal
• limited discrepancy search (LDS)
• large neighborhood search (LNS)
• ...

9
Outline

1 Backtracking Search

2 Search Ordering Heuristics

3 Guiding Search toward Conflicts

10
Search Tree

root
δ1
δ8 δ17
decisions
δ2 δ10 δ18
δ7 δ9
⊥ ⊥
δ3 δ6 δ11
δ4 δ16 δ19
node v, parent of v ′
⊥ ⊥ ⊥
δ5 δ12 δ15
δ13
node v ′ , child of v
⊥ ⊥ ⊥
δ14
dead−ends δk
⊥

leaves solution

11
Nonbinary ϕ-search
Algorithm 1: nonbinary-ϕ-search(P: CN): Boolean
P ← ϕ(P)
if P = ⊥ then
return false
if ∀x ∈ vars(P), |dom(x)| = 1 then
return true
select a variable x of P such that |dom(x)| > 1
foreach value a ∈ dom(x) do
if nonbinary-ϕ-search(P|x=a ) then
return true
return false

Remark.
ϕ denotes the process (level) of filtering under the form of a consistency
to enforce (AC, BC, ...).

12
Nonbinary ϕ-search
Algorithm 2: nonbinary-ϕ-search(P: CN): Boolean
P ← ϕ(P)
if P = ⊥ then
return false
if ∀x ∈ vars(P), |dom(x)| = 1 then
return true
select a variable x of P such that |dom(x)| > 1
foreach value a ∈ dom(x) do
if nonbinary-ϕ-search(P|x=a ) then
return true
return false

Remark.
ϕ denotes the process (level) of filtering under the form of a consistency
to enforce (AC, BC, ...).

12
Illustration
For simplicity, we assume that the domains of all variables is
{1, 2, . . . , d}.

1 x=
x= d

2
...

=
x
1 y 1 z
y= = z= =
d d
2

2
... ...
=

=
y

z
1 z=
z= d
2

...
=
z

Remark.
Note that all taken decisions are positive, i.e., variable assignments.

13
Illustration
For simplicity, we assume that the domains of all variables is
{1, 2, . . . , d}.

1 x=
x= d

2
...

=
x
1 y 1 z
y= = z= =
d d
2

2
... ...
=

=
y

z
1 z=
z= d
2

...
=
z

Remark.
Note that all taken decisions are positive, i.e., variable assignments.

13
Binary ϕ-search

Algorithm 3: binary-ϕ-search(P: CN): Boolean

P ← ϕ(P)
if P = ⊥ then
return false
if ∀x ∈ vars(P), |dom(x)| = 1 then
return true
select a value (x, a) of P such that |dom(x)| > 1
return binary-ϕ-search(P|x=a ) ∨ binary-ϕ-search(P|x̸=a )

Question: Is there a condition on ϕ ?

Answer: ϕ must at least check covered constraints (also true for
nonbinary ϕ-search)

14
Binary ϕ-search

Algorithm 4: binary-ϕ-search(P: CN): Boolean

P ← ϕ(P)
if P = ⊥ then
return false
if ∀x ∈ vars(P), |dom(x)| = 1 then
return true
select a value (x, a) of P such that |dom(x)| > 1
return binary-ϕ-search(P|x=a ) ∨ binary-ϕ-search(P|x̸=a )

Question: Is there a condition on ϕ ?

Answer: ϕ must at least check covered constraints (also true for
nonbinary ϕ-search)

14
Binary ϕ-search

Algorithm 5: binary-ϕ-search(P: CN): Boolean

P ← ϕ(P)
if P = ⊥ then
return false
if ∀x ∈ vars(P), |dom(x)| = 1 then
return true
select a value (x, a) of P such that |dom(x)| > 1
return binary-ϕ-search(P|x=a ) ∨ binary-ϕ-search(P|x̸=a )

Question: Is there a condition on ϕ ?

Answer: ϕ must at least check covered constraints (also true for
nonbinary ϕ-search)

14
Illustration

1
=
...

xy
1

6=
=

1
y
z 6=

z 6=
1

1
z=

z=
1

1
...

z 6=

y 6=
2

2
...
z=

y=
2

2
... ...

Remark.
Note that first decisions are positive, i.e., variable assignments, and
second decisions are negative, i.e., value refutations.
15
Illustration

1
=
...

xy
1

6=
=

1
y
z 6=

z 6=
1

1
z=

z=
1

1
...

z 6=

y 6=
2

2
...
z=

y=
2

2
... ...

Remark.
Note that first decisions are positive, i.e., variable assignments, and
second decisions are negative, i.e., value refutations.
15
About Node Expansion

At each node η of the search tree, there is a subdivision of the current

CN P η into a set of reduced CNs whose union is equivalent to P η . This
guarantees completeness provided that all CNs are explored.

Branching is the fact of subdividing nodes of the search tree.

Remark.
Other forms of branching, different from:
• non-binary branching
• binary branching
introduced earlier can be considered, as for example,
• (binary) domain splitting
where two branches labelled with x < k and x ≥ k are generated.

16
About Node Expansion

At each node η of the search tree, there is a subdivision of the current

CN P η into a set of reduced CNs whose union is equivalent to P η . This
guarantees completeness provided that all CNs are explored.

Branching is the fact of subdividing nodes of the search tree.

Remark.
Other forms of branching, different from:
• non-binary branching
• binary branching
introduced earlier can be considered, as for example,
• (binary) domain splitting
where two branches labelled with x < k and x ≥ k are generated.

16
About Node Expansion

At each node η of the search tree, there is a subdivision of the current

CN P η into a set of reduced CNs whose union is equivalent to P η . This
guarantees completeness provided that all CNs are explored.

Branching is the fact of subdividing nodes of the search tree.

Remark.
Other forms of branching, different from:
• non-binary branching
• binary branching
introduced earlier can be considered, as for example,
• (binary) domain splitting
where two branches labelled with x < k and x ≥ k are generated.

16
Look-ahead and Look-back Schemes

Depending on the chosen level of filtering corresponding to ϕ, we obtain

different look-ahead algorithms. Classical algorithms are:
• BT
• FC (Forward Checking)
• MAC (Maintaining Arc Consistency)

Remark.
There exist look-back schemes that allo us to perform intelligent
backtracking:
• CBJ (Conflict-directed backjumping)
• DBT (Dynamic Backtracking)

17
Look-ahead and Look-back Schemes

Depending on the chosen level of filtering corresponding to ϕ, we obtain

different look-ahead algorithms. Classical algorithms are:
• BT
• FC (Forward Checking)
• MAC (Maintaining Arc Consistency)

Remark.
There exist look-back schemes that allo us to perform intelligent
backtracking:
• CBJ (Conflict-directed backjumping)
• DBT (Dynamic Backtracking)

17
BT

BT is a nonbinary ϕ-search where at each node ϕ simply checks that all

constraints covered by the current instantiation are satisfied.

Definition
Let I be an instantiation and c be a constraint. c is covered by I iff
scp(c) ⊆ vars(I ).

Example.
Let I = {x = 1, y = 3, z = 2} be an instantiation. we have:
• the constraint x + z = y is covered and satisfied by I
• the constraint w = x is not covered by I
• the constraint x > y is covered but not satisfied by I

18
BT

BT is a nonbinary ϕ-search where at each node ϕ simply checks that all

constraints covered by the current instantiation are satisfied.

Definition
Let I be an instantiation and c be a constraint. c is covered by I iff
scp(c) ⊆ vars(I ).

Example.
Let I = {x = 1, y = 3, z = 2} be an instantiation. we have:
• the constraint x + z = y is covered and satisfied by I
• the constraint w = x is not covered by I
• the constraint x > y is covered but not satisfied by I

18
Illustration of BT

4
3
2
1
a b d

19
Illustration of BT

4
3
2
1
a b d

19
Illustration of BT

4
3
2
1
a b d

19
Illustration of BT

4
3
2
1
a b d

19
Illustration of BT

4
3
2
1
a b d

19
Illustration of BT

4
3
2
1
a b d

19
Illustration of BT

4
3
2
1
a b d

19
Illustration of BT

4
3
2
1
a b d

19
Illustration of BT

4
3
2
1
a b d

19
Illustration of BT

4
3
2
1
a b d

19
Illustration of BT

4
3
2
1
a b d

19
Illustration of BT

4
3
2
1
a b d

19
Illustration of BT

4
3
2
1
a b d

19
Illustration of BT

4
3
2
1
a b d

19
Illustration of BT

4
3
2
1
a b d

19
Illustration of BT

4
3
2
1
a b d

19
Illustration of BT

4
3
2
1
a b d

19
Illustration of BT

4
3
2
1
a b d

19
Illustration of BT

4
3
2
1
a b d

19
Illustration of BT

4
3
2
1
a b d

19
Illustration of BT

4 6 more steps
to nd
3 a solution
2
1
a b d

19
FC
FC (Forward Checking) is a nonbinary ϕ-search where at each node ϕ
enforces arc consistency only on constraints that are almost covered by
the current instantiation.

Definition
Let I be an instantiation and c be a constraint. c is almost covered by I
iff |scp(c) \ vars(I )| = 1.

Example.
Let I = {x = 1, y = 3, z = 2} be an instantiation. we have:
• the constraint x + z = y + w is almost covered by I
• the constraint w = t is neither covered nor almost covered by I

Remark.
FC enforces a partial form of Arc Consistency.

20
FC
FC (Forward Checking) is a nonbinary ϕ-search where at each node ϕ
enforces arc consistency only on constraints that are almost covered by
the current instantiation.

Definition
Let I be an instantiation and c be a constraint. c is almost covered by I
iff |scp(c) \ vars(I )| = 1.

Example.
Let I = {x = 1, y = 3, z = 2} be an instantiation. we have:
• the constraint x + z = y + w is almost covered by I
• the constraint w = t is neither covered nor almost covered by I

Remark.
FC enforces a partial form of Arc Consistency.

20
FC
FC (Forward Checking) is a nonbinary ϕ-search where at each node ϕ
enforces arc consistency only on constraints that are almost covered by
the current instantiation.

Definition
Let I be an instantiation and c be a constraint. c is almost covered by I
iff |scp(c) \ vars(I )| = 1.

Example.
Let I = {x = 1, y = 3, z = 2} be an instantiation. we have:
• the constraint x + z = y + w is almost covered by I
• the constraint w = t is neither covered nor almost covered by I

Remark.
FC enforces a partial form of Arc Consistency.

20
Illustration of FC

4
3
2
1
a b d

21
Illustration of FC

4
3
2
1
a b d

21
Illustration of FC

4
3
2
1
a b d

21
Illustration of FC

4
3
2
1
a b d

21
Illustration of FC

4
3
2
1
a b d

21
Illustration of FC

4
3
2
1
a b d

21
Illustration of FC

4
3
2
1
a b d

21
Illustration of FC

4
3
2
1
a b d

21
Illustration of FC

4
3
2
1
a b d

21
Illustration of FC

4
3
2
1
a b d

21
Illustration of FC

4
3
2
1
a b d

21
Illustration of FC

4
3
2
1
a b d

21
Illustration of FC

4
3
2
1
a b d

21
MAC
MAC is a binary search enforcing (maintaining) Arc Consistency at each
node of the search tree.

In the following algorithm,

• we introduce I that represents a stack with the successive positive
decisions that are taken along the current branch
• we write AC (P, S) for enforcing arc consistency, with Q initialized
with S. Note that:
• S is vars(P) initially, to guarantee AC at the root of the search tree
• S is the variable x involved in the last taken decision during search
• we record information about value removals at each level |I | of the
search tree.

Remark.
We consider here that the level in the search tree corresponds to the
number of taken positive decisions (consequently ignoring negative
decisions in this regard).

22
MAC=Binary-AC-search
Algorithm 6: MAC(P: CN)
consistent ← AC (P, vars(P)) // AC initially enforced
if ¬consistent then
return
I ←∅ // I represents the current instantiation
finished ← false
while ¬finished do
select a value (x, a) of P such that x ∈
/ vars(I )
I .push(x, a)
dom(x).reduceTo(a, |I |) // x is assigned the value a at level |I |
consistent ← AC (P, {x}) // AC maintained after positive decisions
if consistent ∧ |I | = n then
print(I ) // A solution has been found and is printed
consistent ← false // Inserted to keep searching for solutions
while ¬consistent ∧ I ̸= ∅ do
(x, a) ← I .pop()
foreach variable y ∈ vars(P) \ vars(I ) do
dom(y ).restoreAt(|I |)
dom(x).remove(a, |I |) // a is removed from dom(x) at level |I |
if dom(x) = ∅ then
consistent ← false
else
consistent ← AC (P, {x}) // AC maintained after negative decisions

if ¬consistent then
finished ← true

23
Illustration of MAC

4
3
2
1
a b d

24
Illustration of MAC

4
3
2
1
a b d

24
Illustration of MAC

4
3
2
1
a b d

24
Illustration of MAC

4
3
2
1
a b d

24
Illustration of MAC

4
3
2
1
a b d

24
Illustration of MAC

4
3
2
1
a b d

24
Illustration of MAC

4
3
2
1
a b d

24
Experiment with ACE

java -jar pycsp3/solvers/ace/[Link] [Link]

-r_c=max -varh=Dom -ppc=-1 -s=all

where:
• -r_c=max means that the restart cutoff is the maximal value (so
there is no restart)
• -varh=Dom means that we use the variable ordering heuristic
min-dom
• -ppc=-1 means that we use a classical propagation scheme
• -s=all means that we look for all solutions

Comparing BT/FC/MAC :
• BT: add -p=BT
• FC: add -p=FC
• MAC: default value (this is equivalent to add -p=AC)

25
Experiment with ACE

java -jar pycsp3/solvers/ace/[Link] [Link]

-r_c=max -varh=Dom -ppc=-1 -s=all

where:
• -r_c=max means that the restart cutoff is the maximal value (so
there is no restart)
• -varh=Dom means that we use the variable ordering heuristic
min-dom
• -ppc=-1 means that we use a classical propagation scheme
• -s=all means that we look for all solutions

Comparing BT/FC/MAC :
• BT: add -p=BT
• FC: add -p=FC
• MAC: default value (this is equivalent to add -p=AC)

25
Backtracking Information

BT, FC and MAC are backtracking algorithms. And when backtracking,

we have to:
• restore domains
• possibly restore constraints (for example, the structure last used
with AC2001 or the dynamic tables used in STR)

Two classical solutions exist:

• Copying
• All structures that must be backtracked are copied at each level.
• The copy is performed before taking the next decision.
• We have to be careful about the memory!
• On backtrack: use the copy recorded at the right level.
• Trailing:
• Only modifications to structures are recorded.
• On backtrack: undo recorded modifications.

26
Backtracking Information

BT, FC and MAC are backtracking algorithms. And when backtracking,

we have to:
• restore domains
• possibly restore constraints (for example, the structure last used
with AC2001 or the dynamic tables used in STR)

Two classical solutions exist:

• Copying
• All structures that must be backtracked are copied at each level.
• The copy is performed before taking the next decision.
• We have to be careful about the memory!
• On backtrack: use the copy recorded at the right level.
• Trailing:
• Only modifications to structures are recorded.
• On backtrack: undo recorded modifications.

26
Intelligent Backtracking: CBJ
BT, FC and MAC basically performs chronological backtracking, whereas
CBJ performs intelligent backtracking.

For simplicity, we consider binary constraints only, and we consider that ϕ

simply checks covered constraints (as in BT).
The method works as follows:
1 Whenever a new assignment y = b is performed, and happens to be
incompatible with a previously assigned value (x, a), we record a
nogood ¬(x = a ∧ y = b), which can also be written as
x = a → y ̸= b
with x = a being the explanation of y ̸= b. We note:
expl(y ̸= b) = {x = a}.
2 Whenever a domain wipeout occurs (for a variable y ), we can
deduce a new nogood:
∧b∈dominit (y ) expl(y ̸= b)

3 Checking inferred nogoods permit to backtrack more than

chronological backtracking.
27
Intelligent Backtracking: CBJ
BT, FC and MAC basically performs chronological backtracking, whereas
CBJ performs intelligent backtracking.

For simplicity, we consider binary constraints only, and we consider that ϕ

simply checks covered constraints (as in BT).
The method works as follows:
1 Whenever a new assignment y = b is performed, and happens to be
incompatible with a previously assigned value (x, a), we record a
nogood ¬(x = a ∧ y = b), which can also be written as
x = a → y ̸= b
with x = a being the explanation of y ̸= b. We note:
expl(y ̸= b) = {x = a}.
2 Whenever a domain wipeout occurs (for a variable y ), we can
deduce a new nogood:
∧b∈dominit (y ) expl(y ̸= b)

3 Checking inferred nogoods permit to backtrack more than

chronological backtracking.
27
Intelligent Backtracking: CBJ
BT, FC and MAC basically performs chronological backtracking, whereas
CBJ performs intelligent backtracking.

For simplicity, we consider binary constraints only, and we consider that ϕ

simply checks covered constraints (as in BT).
The method works as follows:
1 Whenever a new assignment y = b is performed, and happens to be
incompatible with a previously assigned value (x, a), we record a
nogood ¬(x = a ∧ y = b), which can also be written as
x = a → y ̸= b
with x = a being the explanation of y ̸= b. We note:
expl(y ̸= b) = {x = a}.
2 Whenever a domain wipeout occurs (for a variable y ), we can
deduce a new nogood:
∧b∈dominit (y ) expl(y ̸= b)

3 Checking inferred nogoods permit to backtrack more than

chronological backtracking.
27
Illustration of CBJ

x3 x5
1 1
2 2
1 1
2 2
1 1
2
x2 x1 2
x4 x6

28
Illustration of CBJ

x3 x5
1 1
2 2
1 1
2 2
1 1
2
x2 x1 2
x4 x6

28
Illustration of CBJ

x3 x5
1 1
2 2
1 1
2 2
1 1
2
x2 x1 2
x4 x6

28
Illustration of CBJ

x3 x5
1 1
2 2
1 1
2 2
1 1
2
x2 x1 2
x4 x6

28
Illustration of CBJ

x3 x5
1 1
2 2
1 1
2 2
1 1
2
x2 x1 2
x4 x6

28
Illustration of CBJ

x3 x5
1 1
2 2
1 1
2 2
1 1
2
x2 x1 2
x4 x6

28
Illustration of CBJ

x3 x1 x5
1 1
2 2
1 1
2 2
1 1
2
x2 x1 2
x4 x6

28
Illustration of CBJ

x3 x1 x5
1 1
2 2
1 1
2 2
1 1
2
x2 x1 2
x4 x6

28
Illustration of CBJ

x3 x1 x5
1 1
2 2
1 1
2 2
1 1
2
x2 x1 2
x4 x6

28
Illustration of CBJ

x3 x1 x5
1 1
2 2
1 1
2 2
x1
1 1
2
x2 x1 2
x4 x6

28
Illustration of CBJ

x3 x1 x5
1 1
2 2
1 1
2 2
x1
1 1
2
x2 x1 2
x4 x6

28
Illustration of CBJ

x3 x1 x5
1 1
2 2
1 1
2 2
x1
1 1
2
x2 x1 x5 2
x4 x6

28
Illustration of CBJ

x3 x1 x5
1 1
x1
2 2
1 1
2 2
1 1
2
x2 x1 2
x4 x6

28
Illustration of CBJ

x3 x5
1 1
2 ∅ 2
1 1
2 2
1 1
2
x2 x1 2
x4 x6

28
Outline

1 Backtracking Search

2 Search Ordering Heuristics

3 Guiding Search toward Conflicts

29
Search-guiding Heuristics

Important:
• The order in which variables are assigned by a backtracking search
algorithm has been recognized as a key issue for a long time.
• Using different search ordering heuristics to solve a CSP instance
can lead to drastically different results in terms of efficiency.
• Simply introducing some form of randomization to a given search
ordering heuristic may exhibit a large variability in performance.

Goal of such heuristics: to minimize the size of the search trees

Typically, when conducting a backtrack search, we sollicit:

• a variable ordering heuristic to select the next variable x to be
assigned
• a value ordering heuristic to select the value a to assign to x

30
Search-guiding Heuristics

Important:
• The order in which variables are assigned by a backtracking search
algorithm has been recognized as a key issue for a long time.
• Using different search ordering heuristics to solve a CSP instance
can lead to drastically different results in terms of efficiency.
• Simply introducing some form of randomization to a given search
ordering heuristic may exhibit a large variability in performance.

Goal of such heuristics: to minimize the size of the search trees

Typically, when conducting a backtrack search, we sollicit:

• a variable ordering heuristic to select the next variable x to be
assigned
• a value ordering heuristic to select the value a to assign to x

30
Search-guiding Heuristics

Important:
• The order in which variables are assigned by a backtracking search
algorithm has been recognized as a key issue for a long time.
• Using different search ordering heuristics to solve a CSP instance
can lead to drastically different results in terms of efficiency.
• Simply introducing some form of randomization to a given search
ordering heuristic may exhibit a large variability in performance.

Goal of such heuristics: to minimize the size of the search trees

Typically, when conducting a backtrack search, we sollicit:

• a variable ordering heuristic to select the next variable x to be
assigned
• a value ordering heuristic to select the value a to assign to x

30
Search-guiding Heuristics

General rules to adopt for efficieny:

1 It is better to assign first the variables that belong to the hard parts
of the problem. Fail-first principle:
“To succed, try first where you are most likely to fail”
2 To find quickly a solution, it is better to assign first the value that
most likely belongs to a solution (Succeed-first or Promise principle).
3 The initial variable/value choices are particularly important.

Remark.
Depending on the context, the second rule may not be so important.

31
Search-guiding Heuristics

General rules to adopt for efficieny:

1 It is better to assign first the variables that belong to the hard parts
of the problem. Fail-first principle:
“To succed, try first where you are most likely to fail”
2 To find quickly a solution, it is better to assign first the value that
most likely belongs to a solution (Succeed-first or Promise principle).
3 The initial variable/value choices are particularly important.

Remark.
Depending on the context, the second rule may not be so important.

31
Variable Ordering Heuristics

Basically, a variable ordering heuristic associates a score (real value) with

every variable. Then, we can choose between:
• min: selecting the variable with the lowest score
• max: selecting the variable with the highest score

Example.
• min-dom, simply denoted by dom most of the time, is the heuristic
that selects the variable with the smallest current domain.
• max-deg, simply denoted by deg most of the time, is the heuristic
that selects the variable with the highest degree.

In case of several variables with best equal scores, we need a tie-breaker.

For example, brelaz is dom+deg.

32
Variable Ordering Heuristics

Basically, a variable ordering heuristic associates a score (real value) with

every variable. Then, we can choose between:
• min: selecting the variable with the lowest score
• max: selecting the variable with the highest score

Example.
• min-dom, simply denoted by dom most of the time, is the heuristic
that selects the variable with the smallest current domain.
• max-deg, simply denoted by deg most of the time, is the heuristic
that selects the variable with the highest degree.

In case of several variables with best equal scores, we need a tie-breaker.

For example, brelaz is dom+deg.

32
Variable Ordering Heuristics

Basically, a variable ordering heuristic associates a score (real value) with

every variable. Then, we can choose between:
• min: selecting the variable with the lowest score
• max: selecting the variable with the highest score

Example.
• min-dom, simply denoted by dom most of the time, is the heuristic
that selects the variable with the smallest current domain.
• max-deg, simply denoted by deg most of the time, is the heuristic
that selects the variable with the highest degree.

In case of several variables with best equal scores, we need a tie-breaker.

For example, brelaz is dom+deg.

32
Categories of Variable Ordering Heuristics
Static variable ordering heuristics precomputes ordering before search.
• lexico
• deg and ddeg

Dynamic variable ordering heuristics performs a computation at each

node using the current state.
• dom
• dom/ddeg
• brelaz

Adaptive variable ordering heuristics performs a computation at each

node using the current state and the history (of explored nodes).
• wdeg/dom
• impact, activity
• frba/dom, pick/dom

33
Categories of Variable Ordering Heuristics
Static variable ordering heuristics precomputes ordering before search.
• lexico
• deg and ddeg

Dynamic variable ordering heuristics performs a computation at each

node using the current state.
• dom
• dom/ddeg
• brelaz

Adaptive variable ordering heuristics performs a computation at each

node using the current state and the history (of explored nodes).
• wdeg/dom
• impact, activity
• frba/dom, pick/dom

33
Categories of Variable Ordering Heuristics
Static variable ordering heuristics precomputes ordering before search.
• lexico
• deg and ddeg

Dynamic variable ordering heuristics performs a computation at each

node using the current state.
• dom
• dom/ddeg
• brelaz

Adaptive variable ordering heuristics performs a computation at each

node using the current state and the history (of explored nodes).
• wdeg/dom
• impact, activity
• frba/dom, pick/dom

33
Illustration

Compare the (binary) search trees built by FC on the instance 3-queens

while using:
• the heuristic min-dom, with lexico as tie-breaker
• the anti-heuristic max-dom, with lexico as tie-breaker

3
2
1
a b

34
FC-min-dom on 3-queens

3
2
1
a b

35
FC-min-dom on 3-queens

3
2
1
a b

35
FC-min-dom on 3-queens

3
2
1
a b

35
FC-min-dom on 3-queens

3
2
1
a b

35
FC-min-dom on 3-queens

3
2
1
a b

35
FC-min-dom on 3-queens

3
2
1
a b

35
FC-min-dom on 3-queens

3
2
1
a b

35
FC-min-dom on 3-queens

3
2
1
a b

35
FC-min-dom on 3-queens

3
2
1
a b

35
FC-min-dom on 3-queens

3
2
1
a b

35
FC-min-dom on 3-queens

3
2
1
a b

35
FC-max-dom on 3-queens

3
2
1
a b

36
FC-max-dom on 3-queens

3
2
1
a b

36
FC-max-dom on 3-queens

3
2
1
a b

36
FC-max-dom on 3-queens

3
2
1
a b

36
FC-max-dom on 3-queens

3
2
1
a b

36
FC-max-dom on 3-queens

3
2
1
a b

36
FC-max-dom on 3-queens

3
2
1
a b

36
FC-max-dom on 3-queens

3
2
1
a b

36
FC-max-dom on 3-queens

3
2
1
a b

36
FC-max-dom on 3-queens

3
2
1
a b

36
FC-max-dom on 3-queens

3
2
1
a b

36
FC-max-dom on 3-queens

3
2
1
a b

36
FC-max-dom on 3-queens

3
2
1
a b

36
FC-max-dom on 3-queens

3
2
1
a b

36
FC-max-dom on 3-queens

3
2
1
a b

36
FC-max-dom on 3-queens

3
2
1
a b

36
FC-max-dom on 3-queens

3
2
1
a b

36
FC-max-dom on 3-queens

3
2
1
a b

36
FC-max-dom on 3-queens

3
2
1
a b

36
FC-max-dom on 3-queens

3
2
1
a b

36
FC-max-dom on 3-queens

3
2
1
a b

36
Value Ordering Heuristics

Classical heuristics:
• min-value, max-value
• random
• min-conflicts

For a value (x, a), the conflict count of (x, a) on a CN P is an integer,

denoted by cc(x, a), computed as follows:
P
c∈ctrs(P):x∈scp(c) |{τ ∈ Πy ∈scp(c) dom(y ) \ rel(c) | τ [x] = a}|

Remark.
It is not easy to use min-conflicts when global constraints are present.

37
Value Ordering Heuristics

Classical heuristics:
• min-value, max-value
• random
• min-conflicts

For a value (x, a), the conflict count of (x, a) on a CN P is an integer,

denoted by cc(x, a), computed as follows:
P
c∈ctrs(P):x∈scp(c) |{τ ∈ Πy ∈scp(c) dom(y ) \ rel(c) | τ [x] = a}|

Remark.
It is not easy to use min-conflicts when global constraints are present.

37
Outline

1 Backtracking Search

2 Search Ordering Heuristics

3 Guiding Search toward Conflicts

38
Adaptive Heuristics

A search-guiding heuristic is said to be adaptive when the selection it

performs at a given node of the search tree depends on the current state
of the problem instance as well as on the past states encountered so far.

In other words, some information concerning the sub-tree already

explored is taken into account by an adaptive heuristic to perform its
selection. It implements then a kind of learning, as for example:
• wdeg : constraint weighting
• impacts and activity : memorization of search space reductions
• frba and pick: other ways of weighting constraints
• lc (last conflicts): memorization of the last failed assignments

Remark.
Actually, lc is a meta-reasoning, used in conjunction with a variable
ordering heuristic

39
Adaptive Heuristics

A search-guiding heuristic is said to be adaptive when the selection it

performs at a given node of the search tree depends on the current state
of the problem instance as well as on the past states encountered so far.

In other words, some information concerning the sub-tree already

explored is taken into account by an adaptive heuristic to perform its
selection. It implements then a kind of learning, as for example:
• wdeg : constraint weighting
• impacts and activity : memorization of search space reductions
• frba and pick: other ways of weighting constraints
• lc (last conflicts): memorization of the last failed assignments

Remark.
Actually, lc is a meta-reasoning, used in conjunction with a variable
ordering heuristic

39
Adaptive Heuristics

A search-guiding heuristic is said to be adaptive when the selection it

performs at a given node of the search tree depends on the current state
of the problem instance as well as on the past states encountered so far.

In other words, some information concerning the sub-tree already

explored is taken into account by an adaptive heuristic to perform its
selection. It implements then a kind of learning, as for example:
• wdeg : constraint weighting
• impacts and activity : memorization of search space reductions
• frba and pick: other ways of weighting constraints
• lc (last conflicts): memorization of the last failed assignments

Remark.
Actually, lc is a meta-reasoning, used in conjunction with a variable
ordering heuristic

39
Adaptive Heuristics

A search-guiding heuristic is said to be adaptive when the selection it

performs at a given node of the search tree depends on the current state
of the problem instance as well as on the past states encountered so far.

In other words, some information concerning the sub-tree already

explored is taken into account by an adaptive heuristic to perform its
selection. It implements then a kind of learning, as for example:
• wdeg : constraint weighting
• impacts and activity : memorization of search space reductions
• frba and pick: other ways of weighting constraints
• lc (last conflicts): memorization of the last failed assignments

Remark.
Actually, lc is a meta-reasoning, used in conjunction with a variable
ordering heuristic

39
Adaptive Heuristics

A search-guiding heuristic is said to be adaptive when the selection it

performs at a given node of the search tree depends on the current state
of the problem instance as well as on the past states encountered so far.

In other words, some information concerning the sub-tree already

explored is taken into account by an adaptive heuristic to perform its
selection. It implements then a kind of learning, as for example:
• wdeg : constraint weighting
• impacts and activity : memorization of search space reductions
• frba and pick: other ways of weighting constraints
• lc (last conflicts): memorization of the last failed assignments

Remark.
Actually, lc is a meta-reasoning, used in conjunction with a variable
ordering heuristic

39
Adaptive Heuristics

A search-guiding heuristic is said to be adaptive when the selection it

performs at a given node of the search tree depends on the current state
of the problem instance as well as on the past states encountered so far.

In other words, some information concerning the sub-tree already

explored is taken into account by an adaptive heuristic to perform its
selection. It implements then a kind of learning, as for example:
• wdeg : constraint weighting
• impacts and activity : memorization of search space reductions
• frba and pick: other ways of weighting constraints
• lc (last conflicts): memorization of the last failed assignments

Remark.
Actually, lc is a meta-reasoning, used in conjunction with a variable
ordering heuristic

39
Constraint Weighting

The principle is the following:

• a weight is associated with each constraint,
• everytime a conflict occurs while filtering a constraint c, the weight
associated with c is incremented.
• the weigth of a variable is the sum of the weigths of all its involving
constraints.

The interest is that this heuristic is adaptive, with the expectation to

focus on the hard part(s) of the instance.

40
Constraint Weighting

The principle is the following:

• a weight is associated with each constraint,
• everytime a conflict occurs while filtering a constraint c, the weight
associated with c is incremented.
• the weigth of a variable is the sum of the weigths of all its involving
constraints.

The interest is that this heuristic is adaptive, with the expectation to

focus on the hard part(s) of the instance.

40
Implementation

Algorithm 7: constraintPropagationOn(P: CN): Boolean

Q ← ctrs(P)
while Q ̸= ∅ do
pick and delete c from Q
Xevt ← [Link] () // Xevt denotes the set of variables with
reduced domains (after filtering by means of c)
if ∃x ∈ Xevt such that dom(x) = ∅ then
weight[c] ← weight[c] + 1
return false // global inconsistency detected
foreach c ′ ∈ ctrs(P) such that c ′ ̸= c and Xevt ∩ scp(c ′ ) ̸= ∅ do
add c ′ to Q
return true

41
Illustration with queensKnights-8-3-mul
V7

V6

V5

V4

V3

V2

V1

V0

V8

V10

V9

42
Illustration with queensKnights-8-3-mul
V7

V6

V5

V4

V3

V2

V1

V0

V8

V10

V9

42
Illustration with queensKnights-8-3-mul
V7

V6

V5

V4

V3

V2

V1

V0

V8

V10

V9

42
Illustration with queensKnights-8-3-mul
V7

V6

V5

V4

V3

V2

V1

V0

V8

V10

V9

42
Illustration with scen11-f6
V620 V626
V624 V625
V618 V639V621
V619 V638 V622 V627

V623
V616V617

V535 V293
V534
V287V292
V286

V17
V662 V663
V16

V632 V2
V79 V3
V614V615 V633 V94 V96 V99 V78
V98
V630 V4
V95 V97
V324 V0
V658
V650 V640V641
V325 V669 V631
V613 V656 V11 V651 V1
V612 V5
V513
V510 V646 V644
V645 V657 V10 V668 V667 V652
V203 V26 V461 V50 V666 V654
V659
V511 V24 V51 V665
V512 V25 V27
V670 V642 V329 V664
V655
V653
V210 V671
V48
V330 V643 V637 V660 V328
V202 V636 V661
V70
V71 V49 V327
V211
V72 V331 V303
V13 V326 V302
V73
V208 V647
V460 V648
V209 V18 V12
V63 V649
V204 V509 V502 V19 V21
V205 V149 V140V396
V397 V20
V206 V65V142V504V503 V299
V301
V207 V499 V505
V498
V507 V138 V139
V141 V23 V300
V298
V143 V22
V148 V32
V146 V30
V147 V420V421 V31
V64 V369
V506 V368
V134
V508
V62 V136 V566
V137
V135
V156
V157 V296
V297
V154 V33

V221 V349 V567 V569

V336 V443 V568
V442
V220 V337 V155
V346 V444 V571V570 V575
V348
V224 V347 V34 V445
V411 V371 V304
V305
V36 V187 V7
V548 V406 V577
V37 V370 V184V9V572 V15
V225 V549 V467 V551 V426V410 V468 V186 V576
V47
V46
V231 V191 V427 V407 V553 V6V185 V573
V574
V40
V227V230
V108 V189 V529 V533V35 V532 V564 V469 V8 V310
V14
V528 V466 V550 V565V412
V552
V413 V578 V579 V673
V226 V109 V41 V43
V219 V128
V188 V392 V311
V228
V218 V129 V399V531 V419 V152 V307 V672
V190 V610 V52
V229 V400 V581 V306 V53 V44
V530 V446 V374 V418
V393 V45
V398 V378 V447 V404 V580V391 V153 V394 V42
V222
V223 V459 V435 V611
V131
V401 V449 V375 V439
V133 V215 V390 V434V119 V436 V395
V405V116
V117 V438 V450 V309V628
V465 V192V214 V118 V437 V629
V132 V373 V379 V448 V453 V451 V308
V372 V193 V39
V38
V315 V464 V130 V458 V213
V212 V452
V314 V417 V416 V602
V415V414
V340
V127 V603 V634
V341 V342
V283 V126 V600 V635 V323
V282 V343 V423 V475
V557 V562
V260 V321 V121
V120
V335
V334 V425 V601 V322V474
V556 V320 V598
V563 V408
V409 V339 V424
V261 V599 V476
V338
V518 V250 V151
V422 V440
V403 V150 V477
V519 V402 V171
V169 V441 V493 V478
V251 V175
V170
V168 V174 V492
V163 V246 V430 V431 V479 V481
V361 V472 V583
V253 V473 V582
V162 V247 V360 V172
V173 V482
V100 V166 V495 V480
V263 V252V521V520 V165
V167 V91
V93 V485
V357 V164
V356 V333
V363 V106 V58 V178
V179 V462 V494 V483 V486 V88
V159 V429 V177
V176 V89
V262
V362
V158 V522 V428V101
V61 V107
V470V103
V90
V92 V484 V489
V259
V242 V523 V60 V105 V463 V584
V332 V258 V389V102 V69
V104 V585
V388 V317 V487 V491 V87
V471V454
V457 V238 V86
V243V515 V539 V59 V433V68
V608 V81 V84V455V82V526 V316 V239 V488
V295 V318 V456 V240
V111 V83
V517
V319 V294 V432
V675
V605 V241
V609 V66 V85
V265 V114
V514 V537 V67V110 V558V269 V490
V516V216V197V249 V544
V56
V606
V80 V55 V597 V586
V217 V248 V604V377 V264 V232
V195 V541 V376 V54 V57 V233 V587
V545 V268
V527 V596 V235
V75 V237 V540 V290 V501 V500 V115
V196 V74 V236 V536 V381 V607
V674 V234 V594
V77 V554 V285 V591
V194 V76 V380 V542 V291 V161
V284 V160
V559 V592
V538 V244 V555 V595 V590
V366 V245 V383 V593 V588
V367 V382 V386
V387 V543 V589
V288 V113
V359 V254 V354
V255 V365 V289 V112
V358
V355
V364 V384
V385
V312
V123 V313
V200 V267
V266
V201
V257
V256
V122 V353V352
V350
V351
V275
V274 V29
V28
V524V525

V676
V677
V125 V124
V198
V560
V561
V144 V199
V678
V145V180 V279 V278 V496
V679 V497
V182 V181 V280V281
V183

V546 V547
V276V277

V270 V271

V272
V273

V345
V344

43
Illustration with scen11-f6
V620 V626
V624 V625
V618 V639V621
V619 V638 V622 V627

V623
V616V617

V535 V293
V534
V287V292
V286

V17
V662 V663
V16

V632 V2
V79 V3
V614V615 V633 V94 V96 V99 V78
V98
V630 V4
V95 V97
V324 V0
V658
V650 V640V641
V325 V669 V631
V613 V656 V11 V651 V1
V612 V5
V513
V510 V646 V644
V645 V657 V10 V668 V667 V652
V203 V26 V461 V50 V666 V654
V659
V511 V24 V51 V665
V512 V25 V27
V670 V642 V329 V664
V655
V653
V210 V671
V48
V330 V643 V637 V660 V328
V202 V636 V661
V70
V71 V49 V327
V211
V72 V331 V303
V13 V326 V302
V73
V208 V647
V460 V648
V209 V18 V12
V63 V649
V204 V509 V502 V19 V21
V205 V149 V140V396
V397 V20
V206 V65V142V504V503 V299
V301
V207 V499 V505
V498
V507 V138 V139
V141 V23 V300
V298
V143 V22
V148 V32
V146 V30
V147 V420V421 V31
V64 V369
V506 V368
V134
V508
V62 V136 V566
V137
V135
V156
V157 V296
V297
V154 V33

V221 V349 V567 V569

V336 V443 V568
V442
V220 V337 V155
V346 V444 V571V570 V575
V348
V224 V347 V34 V445
V411 V371 V304
V305
V36 V187 V7
V548 V406 V577
V37 V370 V184V9V572 V15
V225 V549 V467 V551 V426V410 V468 V186 V576
V47
V46
V231 V191 V427 V407 V553 V6V185 V573
V574
V40
V227V230
V108 V189 V529 V533V35 V532 V564 V469 V8 V310
V14
V528 V466 V550 V565V412
V552
V413 V578 V579 V673
V226 V109 V41 V43
V219 V128
V188 V392 V311
V228
V218 V129 V399V531 V419 V152 V307 V672
V190 V610 V52
V229 V400 V581 V306 V53 V44
V530 V446 V374 V418
V393 V45
V398 V378 V447 V404 V580V391 V153 V394 V42
V222
V223 V459 V435 V611
V131
V401 V449 V375 V439
V133 V215 V390 V434V119 V436 V395
V405V116
V117 V438 V450 V309V628
V465 V192V214 V118 V437 V629
V132 V373 V379 V448 V453 V451 V308
V372 V193 V39
V38
V315 V464 V130 V458 V213
V212 V452
V314 V417 V416 V602
V415V414
V340
V127 V603 V634
V341 V342
V283 V126 V600 V635 V323
V282 V343 V423 V475
V557 V562
V260 V321 V121
V120
V335
V334 V425 V601 V322V474
V556 V320 V598
V563 V408
V409 V339 V424
V261 V599 V476
V338
V518 V250 V151
V422 V440
V403 V150 V477
V519 V402 V171
V169 V441 V493 V478
V251 V175
V170
V168 V174 V492
V163 V246 V430 V431 V479 V481
V361 V472 V583
V253 V473 V582
V162 V247 V360 V172
V173 V482
V100 V166 V495 V480
V263 V252V521V520 V165
V167 V91
V93 V485
V357 V164
V356 V333
V363 V106 V58 V178
V179 V462 V494 V483 V486 V88
V159 V429 V177
V176 V89
V262
V362
V158 V522 V428V101
V61 V107
V470V103
V90
V92 V484 V489
V259
V242 V523 V60 V105 V463 V584
V332 V258 V389V102 V69
V104 V585
V388 V317 V487 V491 V87
V471V454
V457 V238 V86
V243V515 V539 V59 V433V68
V608 V81 V84V455V82V526 V316 V239 V488
V295 V318 V456 V240
V111 V83
V517
V319 V294 V432
V675
V605 V241
V609 V66 V85
V265 V114
V514 V537 V67V110 V558V269 V490
V516V216V197V249 V544
V56
V606
V80 V55 V597 V586
V217 V248 V604V377 V264 V232
V195 V541 V376 V54 V57 V233 V587
V545 V268
V527 V596 V235
V75 V237 V540 V290 V501 V500 V115
V196 V74 V236 V536 V381 V607
V674 V234 V594
V77 V554 V285 V591
V194 V76 V380 V542 V291 V161
V284 V160
V559 V592
V538 V244 V555 V595 V590
V366 V245 V383 V593 V588
V367 V382 V386
V387 V543 V589
V288 V113
V359 V254 V354
V255 V365 V289 V112
V358
V355
V364 V384
V385
V312
V123 V313
V200 V267
V266
V201
V257
V256
V122 V353V352
V350
V351
V275
V274 V29
V28
V524V525

V676
V677
V125 V124
V198
V560
V561
V144 V199
V678
V145V180 V279 V278 V496
V679 V497
V182 V181 V280V281
V183

V546 V547
V276V277

V270 V271

V272
V273

V345
V344

43
Illustration with scen11-f6
V620 V626
V624 V625
V618 V639V621
V619 V638 V622 V627

V623
V616V617

V535 V293
V534
V287V292
V286

V17
V662 V663
V16

V632 V2
V79 V3
V614V615 V633 V94 V96 V99 V78
V98
V630 V4
V95 V97
V324 V0
V658
V650 V640V641
V325 V669 V631
V613 V656 V11 V651 V1
V612 V5
V513
V510 V646 V644
V645 V657 V10 V668 V667 V652
V203 V26 V461 V50 V666 V654
V659
V511 V24 V51 V665
V512 V25 V27
V670 V642 V329 V664
V655
V653
V210 V671
V48
V330 V643 V637 V660 V328
V202 V636 V661
V70
V71 V49 V327
V211
V72 V331 V303
V13 V326 V302
V73
V208 V647
V460 V648
V209 V18 V12
V63 V649
V204 V509 V502 V19 V21
V205 V149 V140V396
V397 V20
V206 V65V142V504V503 V299
V301
V207 V499 V505
V498
V507 V138 V139
V141 V23 V300
V298
V143 V22
V148 V32
V146 V30
V147 V420V421 V31
V64 V369
V506 V368
V134
V508
V62 V136 V566
V137
V135
V156
V157 V296
V297
V154 V33

V221 V349 V567 V569

V336 V443 V568
V442
V220 V337 V155
V346 V444 V571V570 V575
V348
V224 V347 V34 V445
V411 V371 V304
V305
V36 V187 V7
V548 V406 V577
V37 V370 V184V9V572 V15
V225 V549 V467 V551 V426V410 V468 V186 V576
V47
V46
V231 V191 V427 V407 V553 V6V185 V573
V574
V40
V227V230
V108 V189 V529 V533V35 V532 V564 V469 V8 V310
V14
V528 V466 V550 V565V412
V552
V413 V578 V579 V673
V226 V109 V41 V43
V219 V128
V188 V392 V311
V228
V218 V129 V399V531 V419 V152 V307 V672
V190 V610 V52
V229 V400 V581 V306 V53 V44
V530 V446 V374 V418
V393 V45
V398 V378 V447 V404 V580V391 V153 V394 V42
V222
V223 V459 V435 V611
V131
V401 V449 V375 V439
V133 V215 V390 V434V119 V436 V395
V405V116
V117 V438 V450 V309V628
V465 V192V214 V118 V437 V629
V132 V373 V379 V448 V453 V451 V308
V372 V193 V39
V38
V315 V464 V130 V458 V213
V212 V452
V314 V417 V416 V602
V415V414
V340
V127 V603 V634
V341 V342
V283 V126 V600 V635 V323
V282 V343 V423 V475
V557 V562
V260 V321 V121
V120
V335
V334 V425 V601 V322V474
V556 V320 V598
V563 V408
V409 V339 V424
V261 V599 V476
V338
V518 V250 V151
V422 V440
V403 V150 V477
V519 V402 V171
V169 V441 V493 V478
V251 V175
V170
V168 V174 V492
V163 V246 V430 V431 V479 V481
V361 V472 V583
V253 V473 V582
V162 V247 V360 V172
V173 V482
V100 V166 V495 V480
V263 V252V521V520 V165
V167 V91
V93 V485
V357 V164
V356 V333
V363 V106 V58 V178
V179 V462 V494 V483 V486 V88
V159 V429 V177
V176 V89
V262
V362
V158 V522 V428V101
V61 V107
V470V103
V90
V92 V484 V489
V259
V242 V523 V60 V105 V463 V584
V332 V258 V389V102 V69
V104 V585
V388 V317 V487 V491 V87
V471V454
V457 V238 V86
V243V515 V539 V59 V433V68
V608 V81 V84V455V82V526 V316 V239 V488
V295 V318 V456 V240
V111 V83
V517
V319 V294 V432
V675
V605 V241
V609 V66 V85
V265 V114
V514 V537 V67V110 V558V269 V490
V516V216V197V249 V544
V56
V606
V80 V55 V597 V586
V217 V248 V604V377 V264 V232
V195 V541 V376 V54 V57 V233 V587
V545 V268
V527 V596 V235
V75 V237 V540 V290 V501 V500 V115
V196 V74 V236 V536 V381 V607
V674 V234 V594
V77 V554 V285 V591
V194 V76 V380 V542 V291 V161
V284 V160
V559 V592
V538 V244 V555 V595 V590
V366 V245 V383 V593 V588
V367 V382 V386
V387 V543 V589
V288 V113
V359 V254 V354
V255 V365 V289 V112
V358
V355
V364 V384
V385
V312
V123 V313
V200 V267
V266
V201
V257
V256
V122 V353V352
V350
V351
V275
V274 V29
V28
V524V525

V676
V677
V125 V124
V198
V560
V561
V144 V199
V678
V145V180 V279 V278 V496
V679 V497
V182 V181 V280V281
V183

V546 V547
V276V277

V270 V271

V272
V273

V345
V344

43
Illustration with scen11-f6
V620 V626
V624 V625
V618 V639V621
V619 V638 V622 V627

V623
V616V617

V535 V293
V534
V287V292
V286

V17
V662 V663
V16

V632 V2
V79 V3
V614V615 V633 V94 V96 V99 V78
V98
V630 V4
V95 V97
V324 V0
V658
V650 V640V641
V325 V669 V631
V613 V656 V11 V651 V1
V612 V5
V513
V510 V646 V644
V645 V657 V10 V668 V667 V652
V203 V26 V461 V50 V666 V654
V659
V511 V24 V51 V665
V512 V25 V27
V670 V642 V329 V664
V655
V653
V210 V671
V48
V330 V643 V637 V660 V328
V202 V636 V661
V70
V71 V49 V327
V211
V72 V331 V303
V13 V326 V302
V73
V208 V647
V460 V648
V209 V18 V12
V63 V649
V204 V509 V502 V19 V21
V205 V149 V140V396
V397 V20
V206 V65V142V504V503 V299
V301
V207 V499 V505
V498
V507 V138 V139
V141 V23 V300
V298
V143 V22
V148 V32
V146 V30
V147 V420V421 V31
V64 V369
V506 V368
V134
V508
V62 V136 V566
V137
V135
V156
V157 V296
V297
V154 V33

V221 V349 V567 V569

V336 V443 V568
V442
V220 V337 V155
V346 V444 V571V570 V575
V348
V224 V347 V34 V445
V411 V371 V304
V305
V36 V187 V7
V548 V406 V577
V37 V370 V184V9V572 V15
V225 V549 V467 V551 V426V410 V468 V186 V576
V47
V46
V231 V191 V427 V407 V553 V6V185 V573
V574
V40
V227V230
V108 V189 V529 V533V35 V532 V564 V469 V8 V310
V14
V528 V466 V550 V565V412
V552
V413 V578 V579 V673
V226 V109 V41 V43
V219 V128
V188 V392 V311
V228
V218 V129 V399V531 V419 V152 V307 V672
V190 V610 V52
V229 V400 V581 V306 V53 V44
V530 V446 V374 V418
V393 V45
V398 V378 V447 V404 V580V391 V153 V394 V42
V222
V223 V459 V435 V611
V131
V401 V449 V375 V439
V133 V215 V390 V434V119 V436 V395
V405V116
V117 V438 V450 V309V628
V465 V192V214 V118 V437 V629
V132 V373 V379 V448 V453 V451 V308
V372 V193 V39
V38
V315 V464 V130 V458 V213
V212 V452
V314 V417 V416 V602
V415V414
V340
V127 V603 V634
V341 V342
V283 V126 V600 V635 V323
V282 V343 V423 V475
V557 V562
V260 V321 V121
V120
V335
V334 V425 V601 V322V474
V556 V320 V598
V563 V408
V409 V339 V424
V261 V599 V476
V338
V518 V250 V151
V422 V440
V403 V150 V477
V519 V402 V171
V169 V441 V493 V478
V251 V175
V170
V168 V174 V492
V163 V246 V430 V431 V479 V481
V361 V472 V583
V253 V473 V582
V162 V247 V360 V172
V173 V482
V100 V166 V495 V480
V263 V252V521V520 V165
V167 V91
V93 V485
V357 V164
V356 V333
V363 V106 V58 V178
V179 V462 V494 V483 V486 V88
V159 V429 V177
V176 V89
V262
V362
V158 V522 V428V101
V61 V107
V470V103
V90
V92 V484 V489
V259
V242 V523 V60 V105 V463 V584
V332 V258 V389V102 V69
V104 V585
V388 V317 V487 V491 V87
V471V454
V457 V238 V86
V243V515 V539 V59 V433V68
V608 V81 V84V455V82V526 V316 V239 V488
V295 V318 V456 V240
V111 V83
V517
V319 V294 V432
V675
V605 V241
V609 V66 V85
V265 V114
V514 V537 V67V110 V558V269 V490
V516V216V197V249 V544
V56
V606
V80 V55 V597 V586
V217 V248 V604V377 V264 V232
V195 V541 V376 V54 V57 V233 V587
V545 V268
V527 V596 V235
V75 V237 V540 V290 V501 V500 V115
V196 V74 V236 V536 V381 V607
V674 V234 V594
V77 V554 V285 V591
V194 V76 V380 V542 V291 V161
V284 V160
V559 V592
V538 V244 V555 V595 V590
V366 V245 V383 V593 V588
V367 V382 V386
V387 V543 V589
V288 V113
V359 V254 V354
V255 V365 V289 V112
V358
V355
V364 V384
V385
V312
V123 V313
V200 V267
V266
V201
V257
V256
V122 V353V352
V350
V351
V275
V274 V29
V28
V524V525

V676
V677
V125 V124
V198
V560
V561
V144 V199
V678
V145V180 V279 V278 V496
V679 V497
V182 V181 V280V281
V183

V546 V547
V276V277

V270 V271

V272
V273

V345
V344

43
Experimental Results

1000

100
dom/wdeg

10

1
1 10 100 1000
dom/ddeg

Pairwise comparison (CPU time) of heuristics when used by MAC to

solve the instances from XCSP constraint solver competition.

44
Different ways of weighting constraints

More specifically, let us focus on the following heuristics learning from

conflicts:
1 wdeg/dom [ECAI’04, ICTAI’19]
2 frba/dom [CP’21]
3 pick/dom [CP’23]

45
wdeg/dom
Algorithm 8: propagate((X , C): CN): Boolean
Q←C
while Q ̸= ∅ do
pick and delete c from Q
X ← filter(c) // X , variables with reduced domains
if ∃x ∈ X | dom(x) = ∅ then
incrementWeight(c)
return false // detected inconsistency
foreach c ′ ∈ C | c ′ ̸= c ∧ X ∩ scp(c ′ ) ̸= ∅ do
Q ← Q ∪ {c ′ }
return true

Each variable x is given a ‘weighted degree’, which is the sum of the

weights over all constraints involving x and at least another future
variable. For each variable x, the score of x according to wdeg/dom is:
P
( c∈C : x∈scp(c)∧|fut(c)|>1 [Link][x])/|dom(x)|

46
frba/dom (1/2)

The heuristic frba/dom (Failure Rate Based Search), selects in priority

the variables that most often lead to a conflict when assigning them.
Two counters are introduced:
• #Conflicts(x), records the number of times a failure has been
observed just by propagating an assignment involving x
• #Assigns(x), the number of times the variable x was assigned

The failure rate of a variable x is then:

#Conflicts(x)
fr (x) =
#Assigns(x)

47
frba/dom (2/2)

In addition, similarly to the factor used for chs, we compute:

1
a(x) =
#Conflicts − Conflict(x) + 1

where #Conflicts is the total number of conflicts and Conflict(x) stores

the last value of #Conflicts when x assigned led to a failure.
The failure rate score of a variable x by frba/dom is then:

fr (x) + a(x)
|dom(x)|

48
pick/dom

To record information about tracked variables, we just need to associate

a counter pick[x] with each variable x of the CN. Initially, this counter
(‘pick degree’) is set to 0.

The heuristic pick/dom is simply defined as follows:

• pick/dom selects in priority the future variable with the highest ratio
‘pick degree to current domain size’. For each variable x, the score
of x according to pick/dom is:

pick[x]
|dom(x)|

49
Three Different Ways of Processing Conflicts

•
v =a
M
Queue
•
w =b w ̸= b x y w z y ... w
•
⊥ E ) cx1 cy1 cw1 cz1 cy1 cw1
x =a =
a
P |x cx2 cy2 cw2 cy2 cw2 L
⊥ ϕ(
cy3 cy3

Figure: Illustration of pivotal moments for collecting information about

conflicts: this correspond to early (E), midway (M) and late (L) processing of
conflicts

50
Last-conflict based Reasoning

java -jar [Link] RLFAP-graph-05-opt_c22.xml

Try this, when adding:

• -varh=WdegOnDom
• -varh=FrbaOnDom
• -varh=PickOnDom
• -varh=WdegOnDom -lc=-1
• -varh=FrbaOnDom -lc=-1
• -varh=PickOnDom -lc=-1
• -rr

51
Last-conflict based Reasoning

The principle is the following: everytime a conflict occurs, the last

assigned variable is selected in priority as long as no consistent value is
found for it.

It looks like a lazy identification of nogoods.

52
Implementation

Algorithm 9: binary-ϕ-searchLC (P: ϕ-consistent CN): Boolean

if P = ⊥ then
return false
if ∀x ∈ vars(P), |dom(x)| = 1 then
return true
if priority ̸= null then
x ← priority
else
x ← [Link]()
a ← [Link] (x)
if ϕ(P|x=a ) = ⊥ then
priority ← x
else
priority ← null
return binary-ϕ-searchLC (ϕ(P|x=a )) ∨ binary-ϕ-searchLC (ϕ(P|x̸=a ))

53
Illustration

xj
aj

6=
=

aj
xj
LC1
xi

x i−
1
−
ai

1
6=
=

a i−
1
−
xi

1
xi
ai

xi
6=
=

ai
xi

⊥
⊥
xi
⊥
testing-set = {xi }

54
Example

x2 x1 0 0 x4
1
2 1 1
2 2
1
2
x0 0 0
1 1 1
2
x3 x6 2 2 x5
Figure: The compatibility graph of a constraint network involving a clique of
constraints of difference and a clique of entailed constraints.

55
 x4 = 1 x3 = 0 x2 = 0 x1 = 0
x4
Example

x3

x2
6=
1 6=

6=
0
0
x4 = 1 x3 = 1
x1 6=
0

x4 x3
6= 6=
1 1
x4 = 1 x3 = 0 x2 = 1

x
3
x4 x2

6=
6= 6=

0
1 1
x4 = 1 x3 = 1
x4 x3
6= 6=
1 1
x4 = 0 x3 = 0 x2 = 0 x1 = 1
x
3

x4
x2

6=
6=

0
6=

0
0

x4 = 0 x3 = 1
x1 6=

x4 x3
6= 6=
1

0 1
x4 = 0 x3 = 0 x2 = 1
x
3

x4 x2
6= 6=
6=

0 1
0

x4 = 0 x3 = 1
x4 x3
6= 6=
0 1
x4 = 0 x3 = 0 x2 = 0 x1 = 2
x
3

x4 x1
x2

6=

6= 6=
0

0 2
6=
0

x4 = 0 x3 = 1
x4 x3
6= 6=
0 1
x4 = 0 x3 = 0 x2 = 1
x
3

x4 x2
Figure: Search tree built by MAC (68 explored nodes).

6= 6=
6=

0 1
0

x4 = 0 x3 = 1
x4 x3
6= 6=
0 1
56
Example

x1 6=
0

x4 = 1 x3 = 0 x2 = 0 x1 = 0
x2 x
6=

1
0
0 4
6=

x1 = 1 x4 = 0
0

0
1
0
1
x3

x4

x1

x1
x4 = 1

x1 = 1
6=

6=

6=

6=
0

1
x4

x4
x4 = 1

priority = x1
6=

6=
1

priority = x4
Figure: Search tree built by MAC-LC1 (21 explored nodes).

57
Generalization

xk
ak

6=
=

ak
xk
LC2

xi

xj
1
−

−
aj
xj

1
6=
=

a j−
1
−
xj

1
xk

xj
aj
xi

6=
aj
xj
LC1 xj
xi
⊥
x i−
1
−

xj
ai

1
6=
=

a i−
1

⊥
−
xi

1
xi
ai

xi
6=
=

ai
xi

⊥
⊥
xi
⊥
testing-set = {xi } testing-set = {xi , xj }
58