Efficient Constraint Propagation Engines

arXiv:cs/0611009v1 [] 2 Nov 2006

CHRISTIAN SCHULTE
School of Information and Communication Technology,
KTH – Royal Institute of Technology,
Isafjordsgatan 39, Electrum 229
SE-164 40 Kista, SWEDEN,
email: cschulte@kth.se.
PETER J. STUCKEY
NICTA Victoria Laboratory, Dept of Comp. Sci. & Soft. Eng.,
University of Melbourne 3010, AUSTRALIA,
email: pjs@cs.mu.oz.au.
Abstract
This paper presents a model and implementation techniques for speeding up constraint propagation. Three fundamental approaches to improving constraint propagation based on propagators as implementations of
constraints are explored: keeping track of which propagators are at fixpoint, choosing which propagator to apply next, and how to combine
several propagators for the same constraint.
We show how idempotence reasoning and events help track fixpoints
more accurately. We improve these methods by using them dynamically
(taking into account current domains to improve accuracy). We define
priority-based approaches to choosing a next propagator and show that
dynamic priorities can improve propagation. We illustrate that the use of
multiple propagators for the same constraint can be advantageous with
priorities, and introduce staged propagators that combine the effects of
multiple propagators with priorities for greater efficiency.

1

Introduction

We consider the problem of solving Constraint Satisfaction Problems (CSPs)
defined in the sense of Mackworth [21], which can be stated briefly as follows:
We are given a set of variables, a domain of possible values for each
variable, and a set (read as conjunction) of constraints. Each constraint is a relation defined over a subset of the variables, limiting
the combination of values that the variables in this subset can take.
The goal is to find a consistent assignment of values to the variables
so that all the constraints are satisfied simultaneously.
1

One widely-adopted approach to solving CSPs combines backtracking tree search
with constraint propagation. This framework is realized in finite domain constraint programming systems, such as SICStus Prolog [18], ILOG Solver [17],
and Gecode [12] that have been successfully applied to many real-life industrial
applications.
At the core of a finite domain constraint programming system is a constraint
propagation engine that repeatedly executes propagators for the constraints of a
problem. Propagators discover and remove values from the domains of variables
that can no longer take part in a solution of the constraints.
Example 1.1 Consider a simple CSP, with variables x1 , x2 , and x3 whose
domain of possible values are respectively x1 ∈ {2, 3, 4}, x2 ∈ {0, 1, 2, 3}, x3 ∈
{−1, 0, 1, 2} and the constraints are x3 = x2 , x1 ≤ x2 + 1, and x1 6= 3.
A propagator for x3 = x2 can determine that x2 6= 3 in any solution of this
constraint since x3 cannot take the value 3. Similarly x3 6= −1. The propagator
then reduces the domains of the variables to x2 ∈ {0, 1, 2} and x3 ∈ {0, 1, 2}. A
propagator for x1 ≤ x2 + 1 can determine that x1 6= 4 since x2 ≥ 3, and x2 6= 0
since x1 ≤ 1 so the domains are reduced to x1 ∈ {2, 3} and x2 ∈ {1, 2}. The
propagator for x1 6= 3 can remove the value 3 from the domain of x1 , leaving
x1 ∈ {2} (or x1 = 2). If we now reconsider the propagator for x3 = x2 we can
reduce domains to x2 ∈ {1, 2} and x3 ∈ {1, 2}. No propagator can remove any
further values.
We have not solved the problem, since we do not know a value for each variable. So after propagation we apply search, usually by splitting the domain of a
variable into two disjoint subsets and considering the resulting two subproblems.
Suppose we split the domain of x2 . One subproblem has x1 ∈ {2}, x2 ∈ {1}
and x3 ∈ {1, 2}. Applying the propagator for x2 = x3 results in x3 ∈ {2}. Since
each variable now takes a fixed value we can check that x1 = 2, x2 = 1, x3 = 1
is a solution to the CSP. The other subproblem has x1 ∈ {2}, x2 ∈ {2} and
x3 ∈ {1, 2}, and leads to another solution.
✷
As can be seen from the example finite domain constraint programming
interleaves propagation with search. In this paper we investigate how to make
a propagation engine as efficient as possible.
There are two important decisions the engine must make: which propagators
should execute, and in which order they should execute. In order to make
constraint propagation efficient, it is clear that the engine needs to take the
following issues into account: avoid unnecessary propagator execution, restrict
propagation to relevant variables, and choose the cheapest possible method for
propagation. In this paper we show how propagation can be speeded up if the
engine takes these issues into account.
The contributions of the paper are as follows:
• We give a formal definition of propagation systems including fixpoint and
event-based optimizations used in current propagation systems.
• We extend event-based propagation systems to use dynamically changing
event sets.
2

• We introduce multiple propagators and staged propagators for a single
constraint for use with propagation queues with priority.
• We give experimental results that clarify the impact of many choices in implementing propagation engines: including idempotence reasoning, static
and dynamic events, basic queuing strategies, priority queues, and staged
propagation.
Plan of the paper The next section introduces propagation-based constraint
solving, followed by a model for constraint propagation systems in Section 3.
Section 4 presents how to optimize propagation by taking idempotence into account, while Section 5 explores the use of event sets. Which propagator should
be executed next is discussed in Section 6, while combination strategies of multiple propagators for the same constraint is discussed in Section 7. Experiments
for each feature are included in the relevant section, and a summary is given in
Section 8. Section 9 concludes.

2

Propagation-based Constraint Solving

This section defines our terminology for the basic components of a constraint
propagation engine. In this paper we restrict ourselves to finite domain integer
constraint solving. Almost all the discussion applies to other forms of finite
domain constraint solving such as for sets and multisets.
Domains A domain D is a complete mapping from a fixed (finite) set of
variables V to finite sets of integers. A false domain D is a domain with D(x) = ∅
for some x ∈ V. A variable x ∈ V is fixed by a domain D, if |D(x)| = 1. The
intersection of domains D1 and D2 , denoted D1 ⊓ D2 , is defined by the domain
D(x) = D1 (x) ∩ D2 (x) for all x ∈ V.
A domain D1 is stronger than a domain D2 , written D1 ⊑ D2 , if D1 (x) ⊆
D2 (x) for all x ∈ V. A domain D1 is stronger than (equal to) a domain D2
w.r.t. variables V , denoted D1 ⊑V D2 (resp. D1 =V D2 ), if D1 (x) ⊆ D2 (x)
(resp. D1 (x) = D2 (x)) for all x ∈ V .
A range is a contiguous set of integers, we use range notation [l .. u] to denote
the range {d ∈ Z | l ≤ d ≤ u} when l and u are integers. A domain is a range
domain if D(x) is a range for all x. Let D′ = range(D) be the smallest range
domain containing D, that is, the unique domain D′ (x) = [inf D(x) .. sup D(x)]
for all x ∈ V.
We shall be interested in the notion of an initial domain, which we denote
Dinit . The initial domain gives the initial values possible for each variable. It
allows us to restrict attention to domains D such that D ⊑ Dinit .
Valuations and constraints An integer valuation θ is a mapping of variables
to integer values, written {x1 7→ d1 , . . . , xn 7→ dn }. We extend the valuation θ
to map expressions and constraints involving the variables in the natural way.
3

Let vars be the function that returns the set of variables appearing in a
valuation. We define a valuation θ to be an element of a domain D, written
θ ∈ D, if θ(xi ) ∈ D(xi ) for all xi ∈ vars(θ).
The infimum and supremum of an expression e with respect to a domain D
are defined as inf D e = inf {θ(e)|θ ∈ D} and supD e = sup {θ(e)|θ ∈ D}.
We can map a valuation θ to a domain Dθ as follows

{θ(x)}
x ∈ vars(θ)
Dθ (x) =
Dinit (x) otherwise
A constraint c over variables x1 , . . . , xn is a set of valuations θ such that
vars(θ) = {x1 , . . . , xn }. We also define vars(c) = {x1 , . . . , xn }.
Propagators We will implement a constraint c by a set of propagators prop(c)
that map domains to domains. A propagator f is a monotonically decreasing
function from domains to domains: f (D) ⊑ D, and f (D1 ) ⊑ f (D2 ) whenever
D1 ⊑ D2 . A propagator f is correct for a constraint c iff for all domains D
{θ | θ ∈ D} ∩ c = {θ | θ ∈ f (D)} ∩ c
This is a very weak restriction, for example the identity propagator is correct
for all constraints c.
A set of propagators F is checking for a constraint c, if for all valuations θ
where vars(θ) = vars(c) the following holds: f (Dθ ) = Dθ for all f ∈ F , iff θ ∈ c.
That is, for any domain Dθ corresponding to a valuation on vars(c), f (Dθ ) is a
fixpoint iff θ is a solution of c. We assume that prop(c) is a set of propagators
that is correct and checking for c.
The output variables output(f ) ⊆ V of a propagator f are the variables
changed by the propagator: x ∈ output(f ) if there exists a domain D such that
f (D)(x) 6= D(x). The input variables input(f ) ⊆ V of a propagator f is the
smallest subset V ⊆ V such that for each domain D: D =V D′ implies that
D′ ⊓f (D) =output(f ) f (D′ )⊓D. Only the input variables are useful in computing
the application of the propagator to the domain.
Example 2.1 [Propagators, input, and output] For the constraint c ≡
x1 ≤ x2 + 1 the function fA defined by fA (D)(x1 ) = {d ∈ D(x1 ) | d ≤ supD x2 +
1} and fA (D)(v) = D(v), v 6= x1 is a correct propagator for c. Its output
variables are {x1 } and its input variables are {x2 }. Let D1 (x1 ) = {1, 5, 8} and
D1 (x2 ) = {1, 5}, then f (D1 ) = D2 where D2 (x1 ) = D2 (x2 ) = {1, 5}.
The propagator fB defined as fB (D)(x2 ) = {d ∈ D(x2 ) | d ≥ inf D x1 − 1}
and fB (D)(v) = D(v), v 6= x2 is another correct propagator for c. Its output
variables are {x2 } and input variables {x1 }.
The set {fA , fB } is checking for c. The domain Dθ1 (x1 ) = Dθ1 (x2 ) = {2}
corresponding to the solution θ1 = {x1 7→ 2, x2 7→ 2} of c is a fixpoint of
both propagators. The non-solution domain Dθ2 (x1 ) = {2}, Dθ2 (x2 ) = {0}
corresponding to the valuation θ2 = {x1 7→ 2, x2 7→ 0} is not a fixpoint (of
either propagator).
✷
4

A propagation solver solv(F, D) for a set of propagators F and an initial
domain D finds the greatest mutual fixpoint of all the propagators f ∈ F . In
other words, solv(F, D) returns a new domain defined by
solv(F, D) = gfp(λd. iter(F, d))(D)

iter(F, D) =

⊓

f ∈F

f (D)

where gfp denotes the greatest fixpoint w.r.t ⊑ lifted to functions.
Note that by inverting the direction of ⊑ we could equally well phrase this
as a least fix point (as in [1]). But the current presentation emphasizes the
reduction of domains as computation progresses.
Domain and bounds propagators A consistency notion C gives a condition
on domains with respect to constraints. A set of propagators F maintains
C-consistency for a constraint c, if solv(F, D) is always C consistent for c.
Many propagators in practice are designed to maintain some form of consistency:
usually domain or bounds. But note that many more do not.
The most successful consistency technique was arc consistency [21], which
ensured that for each binary constraint, every value in the domain of the first
variable, has a supporting value in the domain of the second variable that satisfied the constraint. Arc consistency can be naturally extended to constraints
of more than two variables. This extension has been called generalized arc consistency [24], as well as domain consistency [33, 34] (which is the terminology
we will use), and hyper-arc consistency [22]. A domain D is domain consistent
for a constraint c if D is the least domain containing all solutions θ ∈ D of c,
that is, there does not exist D′ ⊏ D such that θ ∈ D ∧ θ ∈ c → θ ∈ D′ .
Define the domain propagator dom(c), for a constraint c as
dom(c)(D)(x)
dom(c)(D)(x)

=
=

{θ(x) | θ ∈ D ∧ θ ∈ c} where x ∈ vars(c)
D(x)
otherwise

The basis of bounds consistency is to relax the consistency requirement to
apply only to the lower and upper bounds of the domain of each variable x.
There are a number of different notions of bounds consistency [8], we give the
two most common here.
A domain D is bounds(Z) consistent for a constraint c with vars(c) =
{x1 , . . . , xn }, if for each variable xi , 1 ≤ i ≤ n and for each di ∈ {inf D xi , supD xi }
there exist integers dj with inf D xj ≤ dj ≤ supD xj , 1 ≤ j ≤ n, j 6= i such that
θ = {x1 7→ d1 , . . . , xn 7→ dn } is an integer solution of c.
A domain D is bounds(R) consistent for a constraint c with vars(c) =
{x1 , . . . , xn }, if for each variable xi , 1 ≤ i ≤ n and for each di ∈ {inf D xi , supD xi }
there exist real numbers dj with inf D xj ≤ dj ≤ supD xj , 1 ≤ j ≤ n, j 6= i such
that θ = {x1 7→ d1 , . . . , xn 7→ dn } is a real solution of c.
A set of propagators F maintains bounds(α) consistency for a constraint c,
if for all domains D, solv(F, D) is bounds(α) consistent for c.
We can define a bounds(Z) propagator, zbnd(c) for a constraint c as follows:
zbnd(c)(D)

=

D ⊓ range(dom(c)(range(D)))
5

search(Fo , Fn , D)
D := isolv(Fo , Fn , D)
if (D is a false domain)
return false
if (∃x ∈ V.|D(v)| > 1)
choose {c1 , . . . , cm } where C ∧ D |= c1 ∨ · · · ∨ cm
for i ∈ [1 .. m]
if (search(Fo ∪ Fn , prop(ci ), D))
return true
return false
return true

% propagation

% search strategy

Figure 1: Search procedure
It is not straightforward to give a generic description of bounds(R) propagators, rbnd(c), for a constraint c, that just maintains bounds(R) consistency.
Examples 3.2 and 4.3 define three such propagators.

3

Constraint Propagation Systems

A constraint propagation system evaluates the function solv(F, D) during backtracking search. We assume an execution model for solving a constraint problem
with a set of constraints C and an initial domain D0 as follows. We execute
the procedure search(∅, F, D0 ) given in Figure 1 for an initial set of propagators
F = ∪c∈C prop(c). This procedure is used to make precise the optimizations
presented in the remainder of the paper.
Note that the propagators are partitioned into two sets, the old propagators Fo and the new propagators Fn . The incremental propagation solver
isolv(Fo , Fn , D) (to be presented later) takes advantage of the fact that D is
guaranteed to be a fixpoint of the old propagators.
The somewhat unusual definition of search is quite general. The default
search strategy for many problems is to choose a variable x such that |D(x)| > 1
and explore x = inf D x or x ≥ inf D x + 1. This is commonly thought of as
changing the domain D for x to either {inf D x} or {d ∈ D(x) | d > inf D x}.
This framework allows more general strategies, for example x1 ≤ x2 or x1 > x2 .
The basic incremental propagation solver algorithm is given in Figure 2. The
algorithm uses a queue Q of propagators to apply. Initially, Q contains the new
propagators. Each time the while loop is executed, a propagator f is deleted
from the queue, f is applied, and then all propagators that may no longer be
at a fixpoint at the new domain D′ are added to the queue. An invariant of the
algorithm is that at the while statement f (D) = D for all f ∈ F − Q.
The propagation solver isolv leaves two components undefined: choose(Q)
chooses the propagator f ∈ Q to be applied next; new(f, F, D, D′ ) determines
the set of propagators f ′ ∈ F that are not guaranteed to be at their fixpoint at
6

isolv(Fo , Fn , D)
F := Fo ∪ Fn ; Q := Fn
while (Q 6= ∅)
f := choose(Q)
Q := Q − {f }; D′ := f (D)
Q := Q ∪ new(f, F, D, D′ )
D := D′
return D

% select next propagator to apply
% add propagators f ′ ∈ F . . .
% . . . not necessarily at fixpoint at D′

Figure 2: Incremental propagation solver.
the domain D′ . The remainder of the paper investigates how to best implement
these two components.

3.1

Basic Variable Directed Propagation

The core aim of the constraint propagation solver solv(F, D) is to find a domain
that is a mutual fixpoint of all f ∈ F . The incremental solver isolv(Fo , Fn , D)
already takes into account that initially D is a fixpoint of propagators f ∈ Fo .
The role of new is (generally) to return as few propagators f ∈ F as possible.
A basic definition of new is as follows
newinput (f, F, D, D′ ) = {f ′ ∈ F | input(f ′ ) ∩ {x ∈ V | D(x) 6= D′ (x)} =
6 ∅}
Here all propagators f ′ are added whose input variable domains have changed.
By the definition of input variables, if none of them have changed for f ′ , then
f ′ (D′ ) = D′ since f ′ (D) = D if f ′ ∈ F − Q.
Proposition 3.1 newinput maintains the invariant f ′ (D) = D for all f ′ ∈
F − Q at the start of the while loop.
Proof : Consider f ′ ∈ F − Q. Then f ′ (D) = D and if D =input(f ′ ) D′ we have
that D′ ⊓ f ′ (D) =output(f ′ ) f ′ (D′ ) ⊓ D. Then
D′

=
=
=output(f ′ )
=

D′ ⊓ D
D′ ⊓ f ′ (D)
f ′ (D′ ) ⊓ D
f ′ (D′ )

since D′ ⊑ D
since D = f ′ (D)
by definition of input(f ′ )
since f ′ (D′ ) ⊑ D′ ⊑ D

Now D′ =output(f ′ ) f ′ (D′ ) implies D′ = f ′ (D′ ) by the definition of output(f ′ ).
Hence each f ′ in F − Q is at fixpoint at the start of the loop. ✷
The incremental propagation solver isolv with this definition of new (assuming Fo = ∅) is more or less equivalent to the propagation algorithms in [4] and [1,
page 267].

7

Example 3.2 [Incremental propagation] Consider the problem with constraints cC ≡ x1 = 2x2 and cD ≡ x1 = 3x3 represented by the bounds(R)
propagators
fC (D)(x1 ) =
fC (D)(x2 ) =
fC (D)(x) =

D(x1 ) ∩ [2 inf D x2 .. 2 supD x2 ] , 
D(x2 ) ∩ ⌈ 12 inf D x1 ⌉ .. ⌊ 12 supD x1 ⌋ ,
D(x)
x 6∈ {x1 , x2 }

fD (D)(x1 ) =
fD (D)(x3 ) =
fD (D)(x) =

D(x1 ) ∩ [3 inf D x3 .. 3 supD x3 ] , 
D(x3 ) ∩ ⌈ 13 inf D x1 ⌉ .. ⌊ 13 supD x1 ⌋ ,
D(x)
x 6∈ {x1 , x3 },

with initial domains D(x1 ) = [0 .. 17], D(x2 ) = [0 .. 9], and D(x3 ) = [0 .. 6].
Initially no constraint is at fixpoint, so Q = {fC , fD }. fC is selected initially,
and we execute the bounds propagator determining D(x1 ) = [0 .. 16], D(x2 ) =
[0 .. 8]. Since x1 has changed, both fC and fD are added to the queue. Then fD
is executed setting D(x1 ) = [0 .. 15], D(x3 ) = [0 .. 5]. Again both constraints are
re-queued. fC is executed changing the domains to D(x1 ) = [0 .. 14], D(x2 ) =
[0 .. 7]. Then fD changes the domains to D(x1 ) = [0 .. 12], D(x3 ) = [0 .. 4].
Since x1 has changed we have Q = {fC , fD }. Now fC is executed for no change,
and fD is executed for no change. We have reached a fixpoint D(x1 ) = [0 .. 12],
D(x2 ) = [0 .. 6], and D(x3 ) = [0 .. 4].
✷

4

Fixpoint Reasoning

The propagation engine computes a mutual fixpoint of all the propagators.
Clearly, if we can determine that some propagators are at fixpoint without
executing them we can limit the amount of work required by the engine.

4.1

Static Fixpoint Reasoning

A propagator f is idempotent if f (D) = f (f (D)) for all domains D. That is,
applying f to any domain D yields a fixpoint of f .
Example 4.1 [Idempotent propagator] The propagator fE defined by
fE (D)(x1 ) =
fE (D)(x2 ) =
fE (D)(x) =

{d ∈ D(x1 ) | 32 d ∈ D(x2 )}
{d ∈ D(x2 ) | 23 d ∈ D(x1 )}
D(x)

x 6∈ {x1 , x2 }

is the domain propagator for the constraint 3x1 = 2x2 . The propagator fE is
idempotent.
✷
It is not difficult to see that each domain propagator dom(c) is idempotent.
Proposition 4.2 For all constraints c and domains D
dom(c)(D) = dom(c)(dom(c)(D))
8

Proof : Consider θ ∈ c where θ ∈ D. Then by definition θ(x) ∈ dom(c)(D) for all
x ∈ vars(c). Hence θ ∈ dom(c)(D). Since dom(c)(D) ⊑ D we have θ ∈ c∧θ ∈ D
iff θ ∈ c ∧ θ ∈ dom(c)(D). Hence dom(c)(D) = dom(c)(dom(c)(D)). ✷
Example 4.3 [Non-idempotent propagators] While many propagators are
idempotent, some widely used ones are not idempotent. Consider the constraint
3x1 = 2x2 and the propagator fF :


fF (D)(x1 ) = D(x1 ) ∩ ⌈ 23 inf D x2 ⌉ .. ⌊ 32 supD x2 ⌋
fF (D)(x2 ) = D(x2 ) ∩ ⌈ 32 inf D x1 ⌉ .. ⌊ 23 supD x1 ⌋
fF (D)(x) = D(x)
x 6∈ {x1 , x2 }
In almost all constraint programming systems prop(3x1 = 2x2 ) is {fF } where
fF is the bounds(R) propagator for 3x1 = 2x2 . Now fF is not idempotent.
Consider D(x1 ) = [0 .. 3] and D(x2 ) = [0 .. 5]. Then D′ = fF (D) is defined
by D′ (x1 ) = [0 .. 3] ∩ [0 .. ⌊10/3⌋] = [0 .. 3] and D′ (x2 ) = [0 .. 5] ∩ [0 .. ⌊9/2⌋] =
[0 .. 4]. Now D′′ = fF (D′ ) is defined by D′′ (x1 ) = [0 .. 3] ∩ [0 .. ⌊8/3⌋] = [0 .. 2]
and D′′ (x2 ) = [0 .. 4] ∩ [0 .. ⌊9/2⌋] = [0 .. 4]. Hence fF (fF (D)) = D′′ 6= D′ =
fF (D).
✷
We can always create an idempotent propagator f ′ from a propagator f by
defining f ′ (D) = solv({f }, D). Indeed, in some implementations (for example [16]) prop(3x1 = 2x2 ) is defined as the fixpoint of applying fF .
Assume that idem(f ) = {f } if f is an idempotent propagator and idem(f ) =
∅ otherwise. The definition of new is improved by taking idempotence into
account
newsfix (f, F, D, D′ ) = newinput (f, F, D, D′ ) − idem(f )
An idempotent propagator is never put into the queue after application.
Note that without the idempotence optimization each propagator f that
changes the domain is likely to be executed again to check it is at fixpoint. Almost all constraint propagation solvers take into account static fixpoint reasoning (for example ILOG Solver [17], Choco [19], SICStus [18], and Gecode [12]).
Some systems even only allow idempotent propagators (for example Mozart [26]).

4.2

Dynamic Fixpoint Reasoning

Even if a propagator is not idempotent we can often determine that f (D) is
a fixpoint of f for a specific domain D. For simplicity we assume a function
fix(f, D) that returns {f } if it can show that f (D) is a fixpoint for f and ∅
otherwise (of course without calculating f (f (D)), otherwise we gain nothing).
In practice this will be included in the implementation of f .
newdfix (f, F, D, D′ ) = newinput (f, F, D, D′ ) − fix(f, D)
Example 4.4 [Dynamic idempotence] For bounds propagation for linear
equations on range domains we are guaranteed that the propagator is at a fixpoint if there is no rounding required in determining new endpoints [16, Theorem
8].
9

We can define fix(fF , D) for the bounds propagator fF from Example 4.3
for the constraint 3x1 = 2x2 , as returning {fF } if any new bound does not
require rounding, e.g. 2 inf D x2 /3 = ⌈2 inf D x2 /3⌉ or 2 inf D x2 /3 ≤ inf D x1 and
similarly for the other three bounds.
Consider applying fF to the domain D′′ from the same example. Now D′′′ =
fF (D′′ ) is defined by D′′′ (x1 ) = [0 .. 2] ∩ [0 .. ⌊8/3⌋] = [0 .. 2] and D′′′ (x2 ) =
[0 .. 4] ∩ [0 .. ⌊6/2⌋] = [0 .. 3]. Notice that the new bound x2 ≤ 3 is obtained
without rounding ⌊6/2⌋ = ⌊3⌋ = 3. In this case we are guaranteed that the
propagator is at a fixpoint.
✷
Note that the dynamic case extends the static case since for idempotent f it
holds that fix(f, D) = {f } for all domains D. The dynamic fixpoint reasoning
extensions are obviously correct, given Proposition 3.1.
Proposition 4.5 newdfix maintains the invariant f (D) = D for all f ∈ F − Q
at the start of the while loop.
A complexity of either form of fixpoint reasoning is that a great deal of
care has to be taken when we claim a propagator is at fixpoint, particularly for
bounds propagators and for propagators computing with multiple occurrences
of the same variable.
Example 4.6 [Falling into domain holes] Consider a bounds propagator for
x1 = x2 + 1 defined as
fG (D)(x1 )
fG (D)(x2 )
fG (D)(x)

= D(x1 ) ∩ [inf D x2 + 1 .. supD x2 + 1]
= D(x2 ) ∩ [inf D x1 − 1 .. supD x1 − 1]
= D(x)
x 6∈ {x1 , x2 }

We would expect this propagator to be idempotent since there is no rounding
required. Consider the application of fG to the domain D(x1 ) = {0, 4, 5, 6}
and D(x2 ) = {2, 3, 4, 5}. Then fG (D) = D′ where D′ (x1 ) = {4, 5, 6} and
D′ (x2 ) = {2, 3, 4, 5}. This is not a fixpoint for fG because of the hole (that is
1, 2, 4 6∈ D(x1 )) in the original domain of x1 .
✷
Example 4.7 [Multiple variable occurrences] The regular constraint introduced in [27] constrains a sequence of variables to take values described by
a regular expression (or a corresponding finite automaton). A common case for
the regular constraint is to express cyclic patterns by performing propagation
on a sequence of variables where some variables appear multiply.
Assume a propagator fH propagating that the sequence of variables hx1 , x2 , x3 i
conforms to the regular expression (11|00)0 (that is, the values of three variables form either the string 110 or 000).
For a domain D with D(x1 ) = D(x2 ) = D(x3 ) = {0, 1} propagation for
the sequence hx1 , x2 , x3 i is obtained by checking which values are still possible
for each variable by traversing the sequence once. In this particular case, for
D′ = fH (D) we have that D′ (x3 ) = {0} and D′ (x1 ) = D′ (x2 ) = {0, 1} and D′
is a fixpoint for fH .
10

Now assume a sequence hx1 , x2 , x1 i where x1 appears twice. Using the same
strategy as above, a single forward traversal of the sequence yields: D′ = fH (D)
where D′ (x1 ) = {0} and D′ (x2 ) = {0, 1}. However, D′ is not a fixpoint for fH .
✷
The two examples above describe common cases where a propagator is not
idempotent but in many cases still computes a fixpoint. In these cases, dynamic
fixpoint reasoning is beneficial: static fixpoint reasoning would force these propagators to be never considered to be at fixpoint while dynamic fixpoint reasoning
allows the propagator to decide whether the propagator is at fixpoint for a given
domain or not.
In practice dynamic fixpoint reasoning completely subsumes static fixpoint
reasoning and is easy to implement. To implement dynamic fixpoint reasoning
a propagator is extended to not only return the new domain but also a flag
indicating whether it is guaranteed to be at fixpoint.

4.3

Fixpoint Reasoning Experiments

Table 1 shows runtime (walltime) and the number of propagation steps for
the three different variants of fixpoint reasoning considered. The first column
presents absolute runtime values in milliseconds and the number of propagation
steps when no fixpoint reasoning is considered. The two remaining columns
“static” and “dynamic” show the relative change to runtime and propagation
steps when using static and dynamic fixpoint reasoning. For example, a relative
change of +50% means that the system takes 50% more time or propagation
steps, whereas a value of −50% means that the system takes only half the time or
propagation steps. The row “average (all)” gives the average (geometric mean)
of the relative values for all examples. More information on the examples can
be found in Appendix A and on the used platform in Appendix B.
Note that both static and dynamic fixpoint reasoning do not change the
memory requirements for any of the examples.
Static fixpoint reasoning While static fixpoint reasoning reduces the number of propagator executions by 8.9% in average, the reduction in runtime is
modest by 1.6% in average. The reason that the reduction in propagation steps
does not directly translate to a similar reduction in runtime is that the avoided
steps tend to be cheap: after all, these are steps not performing any propagation
as the propagator is already at fixpoint. Examples with significant reduction
in runtime (such as donald-d, minsort-200, picture, and square-5-d) profit
because the execution of costly propagators is avoided (domain-consistent linear equations for donald-d and square-5-d; regular propagators for picture;
minimum propagators involving up to 200 variables for minsort). The behavior
of golomb-10-b and golomb-10-d is explained further below.
Dynamic fixpoint reasoning As expected, both runtime as well as propagation steps are considerably smaller for dynamic fixpoint reasoning compared
11

Table 1: Fixpoint reasoning experiments.
Example
all-interval-500
alpha
bibd-7-3-60
cars
crowded-chess-7
donald-b
donald-d
donald-v
golomb-10-b
golomb-10-d
graph-color
grocery
knights-10
minsort-200
o-latin-7-d
partition-32
photo
picture
queens-400
queens-400-a
sequence-500
square-5-d
square-7-b
square-7-v
warehouse
average (all)

none
time (ms)
steps
118.31
503 036
106.56
272 398
2 279.36
1 335 657
4.64
15 641
624.25
806 664
0.70
546
30.37
46
0.38
546
1 347.48
2 642 464
2 430.00
2 642 962
35.87
9 344
55.41
2 299
7.46
48 038
342.48
240 991
574.36
387 060
8 571.24
16 785 128
108.87
422 206
1 553.42
150 165
4 433.12
31 424 152
16.15
2 469
517.96
151 609
33 391.24
1 762 492
10 166.24
7 731 557
5 690.00
13 956 982
0.74
2 486
—
—

12

static
time
steps
−3.1%
−24.8%
−2.0%
−5.7%
−0.2%
−6.5%
−0.4%
±0.0%
−0.1%
±0.0%
−2.5%
−8.4%
−6.3%
−6.5%
−5.9%
−16.5%
+4.7%
−17.9%
+4.5%
−18.0%
−0.1%
±0.0%
+2.6%
−3.8%
+0.9%
+2.2%
−11.3%
−8.3%
±0.0%
−0.5%
−3.7%
−18.8%
−0.3%
−0.8%
−4.1%
−13.1%
+0.2%
±0.0%
−1.2%
−16.2%
−0.1%
−0.1%
−6.2%
−16.0%
+2.4%
−14.5%
−4.1%
−16.9%
−2.5%
−1.8%
−1.6%
−8.9%

dynamic
time
steps
−38.9%
−24.9%
−1.5%
−5.7%
−0.2%
−6.5%
+0.1%
±0.0%
−0.2%
±0.0%
−10.4%
−16.5%
−6.4%
−13.0%
−5.1%
−16.5%
+0.1%
−17.5%
+4.3%
−18.0%
−7.2%
−6.2%
+2.6%
−3.8%
+0.9%
+2.2%
−5.1%
−16.9%
−8.7%
−18.2%
−9.2%
−19.7%
−14.6%
−3.6%
−3.4%
−20.5%
±0.0%
±0.0%
−1.2%
−16.2%
−0.1%
−0.1%
−6.1%
−16.1%
−6.8%
−14.7%
−4.3%
−16.9%
−7.9%
−9.1%
−5.6%
−11.5%

Table 2: Fixpoint reasoning experiments with propagator priorities.
Example
all-interval-500
alpha
bibd-7-3-60
cars
crowded-chess-7
donald-b
donald-d
donald-v
golomb-10-b
golomb-10-d
graph-color
grocery
knights-10
minsort-200
o-latin-7-d
partition-32
photo
picture
queens-400
queens-400-a
sequence-500
square-5-d
square-7-b
square-7-v
warehouse
average (all)

static
time
steps
−2.9% −24.9%
−5.4% −15.6%
−0.7%
−6.5%
−0.2%
±0.0%
−0.7%
±0.0%
−4.8% −22.9%
−6.7%
−5.1%
−5.6% −16.5%
−4.9% −23.5%
−3.3% −23.4%
+0.4%
±0.0%
−4.9% −29.5%
±0.0%
+1.3%
−10.9%
−9.1%
+0.3%
−1.4%
−8.5% −30.4%
−0.7%
−1.2%
+6.5% −13.1%
+0.2%
±0.0%
−1.3% −16.2%
+0.1%
±0.0%
−6.4% −11.1%
−2.5% −25.2%
−6.6% −24.9%
−2.2%
−1.4%
−2.9% −12.7%

dynamic
time
steps
−37.7%
−25.0%
−4.6%
−15.6%
−0.7%
−6.5%
+0.1%
±0.0%
−0.5%
±0.0%
−11.8%
−29.4%
−6.7%
−28.8%
−5.3%
−16.5%
−6.5%
−23.5%
−3.0%
−23.4%
−7.3%
−4.9%
−4.9%
−29.5%
+0.2%
+1.3%
−0.9%
−9.2%
−6.1%
−22.9%
−11.8%
−30.9%
−7.5%
−2.6%
+4.0%
−20.5%
+0.2%
±0.0%
−1.3%
−16.2%
+0.1%
±0.0%
−7.3%
−15.8%
−10.0%
−26.0%
−5.8%
−24.9%
−7.9%
−9.8%
−6.1%
−15.9%

to static reasoning. This is in particular true for examples donald-b and
square-7-b where a bounds-consistent alldifferent constraint can take advantage of reporting whether propagation has computed a fixpoint due to no
domain holes as discussed in Example 4.6 (all-interval-500 shows the same
behavior due to the absolute value propagator used).
Influence of propagation order Some examples show a considerable increase in runtime (in particular, golomb-10-b and golomb-10-d). This is due
to the fact that the order in which propagators are executed changes: costly
propagators are executed often while cheap propagators are executed less often
(witnessed by the decrease in propagation steps).
Section 6 presents priorities that order execution according to propagator
priorities. For now it is sufficient to note that when these priority inversion
problems are avoided through the use of priorities, there is no increase in runtime. Table 2 provides evidence for this. The table shows relative runtime
and propagation steps (relative to no fixpoint reasoning as in Table 1). When
avoiding priority inversion it becomes clear that both static as well as dynamic
13

fixpoint reasoning consistently improve the number of propagation steps and
also runtime. The only exception is picture where even with priorities the
considerable reduction in execution steps does not translate into a reduction in
runtime. This is possibly due to a change in propagation order that affects runtime (that this can have a remarkable effect even with priorities is demonstrated
in Section 6).

5

Event Reasoning

The next improvement for avoiding propagators to be put in the queue is to
consider what changes in domains of input variables can cause the propagator
to no longer be at a fixpoint. To this end we use events: an event is a change
in the domain of a variable.
Assume that the domain D changes to the domain D′ ⊑ D. A typical set of
events defined in a constraint propagation system are:
• fix(x): the variable x becomes fixed, that is |D′ (x)| = 1 and |D(x)| > 1.
• lbc(x): the lower bound of variable x changes, that is inf D′ x > inf D x.
• ubc(x): the upper bound of variable x changes, that is supD′ x < supD x.
• dmc(x): the domain of variable x changes, that is D′ (x) ⊂ D(x).
Clearly the events overlap. Whenever a fix(x) event occurs then a lbc(x) event,
a ubc(x) event, or both events must also occur. If any of the first three events
occur then a dmc(x) event occurs. These events satisfy the following property.
Definition 5.1 [Event] An event φ is a change in domain defined by an event
condition φ(D, D′ ) which states that event φ occurs when the domain changes
from D to D′ ⊑ D. The event condition must satisfy the following property
φ(D, D′′ ) = φ(D, D′ ) ∨ φ(D′ , D′′ )
where D′′ ⊑ D′ ⊑ D. So an event occurs on a change from D to D′′ iff it occurs
in either the change from D to D′ or from D′ to D′′ .
Given a domain D and a stronger domain D′ ⊑ D, then events(D, D′ ) is the
set of events φ where φ(D, D′ ). Suppose D′′ ⊑ D′ ⊑ D, then clearly
events(D, D′′ ) = events(D, D′ ) ∪ events(D′ , D′′ ).

(1)

Most integer propagation solvers use the events defined above, although
many systems collapse ubc(x) and lbc(x) into a single event bc(x) (for example, SICStus [18], ILOG Solver [17], and Gecode [12]). Choco [19] maintains
an event queue and interleaves propagator execution with events causing more
propagators to be added to the queue.
Other kinds of events or variants of the above events are also possible. For
example, (for domains D and D′ with D′ ⊑ D):
14

• bc(x): as discussed above (lbc(x) ∨ ubc(x)).
• two(x): the variable x reduces to a domain of at most two values: |D′ (x)| ≤
2 and |D(x)| > 2.
• ran(x): the variable x reduces to a domain that will always be a range
(two consecutive values or a single value): supD′ x − inf D′ x ≤ 1 and
supD x − inf D > 1.
• pos(x): the variable x reduces to a domain that is strictly positive, that
is inf ′D x > 0 and inf D x ≤ 0 (likewise, an event neg(x) for reduction to a
strictly negative domain).
• nneg(x): the variable x reduces to a domain that is non-negative: inf ′D x ≥
0 and inf D x < 0 (likewise, an event npos(x) for reduction to a non-positive
domain).
• neq(x, d): the variable x can no longer take the value d, that is d ∈ D(x)
and d 6∈ D′ (x)
The events two and ran are useful for tracking endpoint-relevance and rangeequivalence [31]. The neq event has been used in e.g. Choco [19] and BProlog [37] for building AC4 [23] style propagators.
Example 5.2 [Events] Let D(x1 ) = {1, 2, 3}, D(x2 ) = {3, 4, 5, 6}, D(x3 ) =
{0, 1}, and D(x4 ) = {7, 8, 10} while D′ (x1 ) = {1, 2}, D′ (x2 ) = {3, 5, 6}, D′ (x3 ) =
{1} and D′ (x4 ) = {7, 8, 10}. Then events(D, D′ ) is
{ubc(x1 ), dmc(x1 ), dmc(x2 ), fix(x3 ), lbc(x3 ), dmc(x3 )}
Considering the additional events we obtain in addition
{bc(x1 ), two(x1 ), ran(x1 ), bc(x3 ), neq(x1 , 3), neq(x2 , 4), neq(x3 , 0)}
✷
Example 5.3 [Events are monotonic] Events are monotonic: further changes
to a domain do not discard events from previous changes. Consider the property
range(x) capturing that D(x) is a range for a domain D (this property is related
to the event ran(x), lacking the restriction that the domain can have at most
two elements).
The property range(x) is not an event: consider domains D′′ ⊑ D′ ⊑ D
with D(x) = {1, 2, 3, 5}, D′ (x) = {1, 2, 3}, and D′′ (x) = {1, 3}. If range were
an event, then events(D, D′′ ) = events(D, D′ ) ∪ events(D′ , D′′ ). However,
events(D, D′′ ) = {dmc(x), ubc(x)}
whereas
events(D, D′ ) ∪ events(D′ , D′′ ) = {dmc(x), ubc(x), range(x)} ∪ {dmc(x)}
✷
15

5.1

Static Event Sets

Re-execution of certain propagators can be avoided since they require certain
events to generate new information.
Definition 5.4 [Propagator dependence] A propagator f is dependent on
a set of events es(f ) iff
(a) for all domains D if f (D) 6= f (f (D)) then events(D, f (D)) ∩ es(f ) 6= ∅,
(b) for all domains D and D′ where f (D) = D, D′ ⊑ D and f (D′ ) 6= D′ then
events(D, D′ ) ∩ es(f ) 6= ∅.
The definition captures the following. If f is not at a fixpoint then one of
the events in its event set occurs. If f is at a fixpoint D then any change to a
domain that is not a fixpoint D′ involves an occurrence of one of the events in
its set. Note that for idempotent propagators the case (a) never occurs.
For convenience later we will store the event set chosen for a propagator f
in an array evset[f ].
Clearly, if we keep track of the events since the last invocation of a propagator, we do not need to apply a propagator if it is not dependent on any of these
events.
Example 5.5 [Event sets] Event sets for previously discussed propagators are
as follows:
fA
{ubc(x2 )}
fB
{lbc(x1 )}
fE
{dmc(x1 ), dmc(x2 )}
fF
{lbc(x1 ), ubc(x1 ), lbc(x2 ), ubc(x2 )}
This is easy to see from the definitions of these propagators. If they use inf D x
then lbc(x) is in the event set, similarly if they use supD x then ubc(x) is in the
event set. If they use the entire domain D(x) then dmc(x) is in the event set.
✷
Indexical propagation solvers [34, 9, 6] are based on such reasoning. They
define propagators in the form f (D)(x) = D(x) ∩ e(D) where e is an indexical
expression. The event set for such propagators is automatically defined by the
domain access terms that occur in the expression e.
Example 5.6 [Indexical] An example of an indexical to propagate x1 ≥ x2 +1
is
x1 ∈ [inf(x2 ) + 1 .. + ∞]
x2 ∈ [−∞ .. sup(x1 ) − 1]
These range expressions for indexicals define two propagators:
fI (D)(x1 )
fI (D)(x)
fJ (D)(x2 )
fJ (D)(x)

=
=
=
=

D(x1 ) ∩ [inf(x2 ) + 1 .. + ∞]
D(x)
x 6= x1
D(x2 ) ∩ [−∞ .. sup(x1 ) − 1]
D(x)
x=
6 x2
16

The event set for the propagator fI from the definition is {lbc(x2 )} while
the the event set for fJ is {ubc(x1 )}.
✷
Using events we can define a much more accurate version of new that only
adds propagators for which one of the events in its event set has occurred.
newevents (f, F, D, D′ ) = {f ′ ∈ F | evset[f ′ ] ∩ events(D, D′ ) 6= ∅} − fix(f, D)
This version of new (without dynamic fixpoint reasoning) roughly corresponds
with what most constraint propagation systems currently implement.
Proposition 5.7 newevents maintains the invariant f (D) = D for all f ∈ F −Q
at the start of the while loop.
Proof : Consider f ′ ∈ F − Q − {f } different from the selected propagator f .
Then f ′ (D) = D and if f ′ (D′ ) 6= D′ then events(D, D′ ) ∩ es(f ′ ) 6= ∅ by case (b)
of the definition of es(f ′ ), so f ′ ∈ Q at the start of the loop.
Consider selected propagator f . This is removed from Q, but if f (D′ ) 6= D′
then events(D, D′ ) ∩ es(f ) 6= ∅ by case (a) of the definition of es(f ). Clearly
also fix(f, D) 6= ∅. So f ∈ Q at the start of the loop. ✷

5.2

Event Set Experiments

Table 3 shows runtime and number of propagation steps for different event
sets relative to a propagation engine not using events (the engine uses dynamic
fixpoint reasoning but no priorities). The row “average (above)” gives the geometric mean of the relative numbers given in the table whereas “average (all)”
shows the relative numbers for all examples.
General observations A first, quite surprising, observation is that using no
events at all is not so bad. It is the best approach for 10 out of the 25 benchmarks
and for crowded-chess-7 by a considerable margin (between 8.3% and 38.7%).
Another general observation is that a reduction in the number of propagation
steps does not directly translate into a reduction in runtime. This is due to the
fact that all saved propagator executions are cheap: the propagator is already
at fixpoint and does not have to perform propagation.
Note that the ratio between reduction in steps and reduction in runtime
ultimately depends on the underlying system. In Gecode, the system used, the
actual overhead for executing a propagator is rather low. In systems with higher
overhead one can expect that the gain in runtime will be more pronounced.
Event set observations Adding the fix event is particularly beneficial for
benchmarks with many disequalities, particularly queens-400 which only uses
disequalities.
Adding the bc event has significant benefit (up to 5%) when there are linear
equalities as in alpha or bounds(Z) consistent alldifferent as in photo. But

17

Table 3: Event set experiments (runtime and propagation steps).
Example
all-interval-500
alpha
bibd-7-3-60
cars
crowded-chess-7
donald-b
donald-d
donald-v
golomb-10-b
golomb-10-d
graph-color
grocery
knights-10
minsort-200
o-latin-7-d
partition-32
photo
picture
queens-400
queens-400-a
sequence-500
square-5-d
square-7-b
square-7-v
warehouse
average (all)

only fix, dmc
time
steps
+0.6%
±0.0%
−2.0%
−4.4%
−2.6%
−16.6%
+1.1%
−0.2%
+8.3%
±0.0%
+0.3%
±0.0%
±0.0%
±0.0%
+0.6%
−10.5%
−0.6%
±0.0%
+0.2%
±0.0%
−0.7%
−47.7%
−0.1%
±0.0%
−12.7%
−47.5%
+0.4%
±0.0%
−1.2%
±0.0%
+0.7%
±0.0%
+1.6%
±0.0%
+2.0%
±0.0%
−87.5%
−99.1%
−10.4%
−38.8%
+2.2%
±0.0%
+0.8%
±0.0%
−0.2%
+0.5%
−1.0%
−8.9%
+2.2%
+0.2%
−8.5%
−24.3%

with
time
+1.0%
−7.3%
−1.4%
+1.7%
+20.2%
−2.1%
+0.9%
−1.4%
±0.0%
+26.4%
+0.1%
±0.0%
−10.8%
+1.1%
+0.2%
+15.1%
−3.3%
+3.5%
−87.5%
−9.6%
+3.5%
+2.7%
+0.6%
−1.7%
+3.3%
−6.7%

18

bc
steps
±0.0%
−19.2%
−16.6%
−0.2%
−8.4%
−9.2%
±0.0%
−19.7%
−3.9%
−3.5%
−49.5%
±0.0%
−48.6%
±0.0%
−1.7%
+3.4%
−27.1%
±0.0%
−99.1%
−38.8%
+36.3%
±0.0%
−8.2%
−16.9%
−7.6%
−26.9%

with lbc, ubc
time
steps
+2.0%
±0.0%
−6.3%
−19.3%
+7.4%
−15.8%
+2.6%
−0.2%
+38.7%
−8.4%
−1.3%
−9.2%
−0.1%
±0.0%
+0.1%
−19.7%
−0.5%
−3.9%
+26.5%
−3.5%
+0.6%
−49.5%
±0.0%
±0.0%
−7.7%
−48.6%
+1.5%
±0.0%
+1.5%
−1.7%
+18.8%
+17.7%
−2.0%
−26.9%
+11.5%
±0.0%
−87.5%
−99.1%
−8.2%
−38.8%
+8.8%
+36.3%
+2.6%
+0.5%
+0.7%
−7.8%
+1.2%
−16.9%
+4.2%
−6.6%
−4.6%
−26.4%

Table 4: Event set experiments with priorities (runtime and propagation steps).
Example
bibd-7-3-60
crowded-chess-7
donald-b
donald-d
golomb-10-b
golomb-10-d
minsort-200
partition-32
picture
square-5-d
square-7-b
average (above)
average (all)

only fix, dmc
time
steps
+6.1%
−3.3%
+8.0%
±0.0%
+0.9%
±0.0%
−0.3%
±0.0%
+0.1%
±0.0%
+0.1%
±0.0%
+0.9%
±0.0%
+1.9%
−1.2%
+2.6%
±0.0%
+0.9%
±0.0%
+0.4%
−0.1%
+1.9%
−0.4%
−7.8% −24.1%

with
time
+0.6%
+20.4%
−1.1%
+0.1%
−0.9%
−0.5%
+1.5%
+1.8%
+3.7%
+3.2%
+0.2%
+2.5%
−7.8%

bc
steps
−3.3%
−0.7%
−9.2%
±0.0%
−5.5%
−7.8%
±0.0%
−1.8%
±0.0%
±0.0%
−10.6%
−3.6%
−27.8%

with lbc, ubc
time
steps
+13.1%
−2.5%
+38.0%
−0.7%
−0.7%
−9.2%
−0.2%
±0.0%
−0.9%
−5.5%
±0.0%
−7.8%
+1.8%
±0.0%
+1.0%
−0.4%
+1.6%
±0.0%
+3.2%
+0.2%
+1.2% −10.6%
+4.8%
−3.4%
−6.3% −27.7%

for other examples, where one would expect some reduction in runtime, the overhead (to be discussed in more detail below) for maintaining a richer event set
exceeds the gains from reducing the number of propagation steps. This is true for
examples such as minsort-200 (minimum propagators), partition-32 (multiplication), and golomb-10-b and square-7-b (linear equations and bounds(Z)
consistent alldifferent).
Splitting the bc event into lbc and ubc events exposes the overhead once
more. There is almost never an improvement in number of propagations, since
only inequalities can actually benefit, and there is substantial overhead.
Influence of propagation order Similar to using fixpoint reasoning, the
use of events also changes the order in which propagators are executed. Table 4
reconsiders all examples that could possibly benefit from bc or lbc, ubc events
and all examples that show a remarkable increase in number of propagation
steps in Table 3.
The numbers confirm that with priorities no considerable increase in runtime
can be observed for all but crowded-chess-7, where the increase in runtime here
is due to a change in propagation order to the introduction of event sets that
does not depend on the relative priorities of the propagators used.
Once priorities are used, lbc and ubc are basically never beneficial.
Memory requirements Table 5 shows the total memory allocated for different event sets relative to a propagation engine not using events (the engine
uses dynamic fixpoint reasoning and priorities). It is important to note that the
memory figures reflect the amount of memory allocated which is bigger than
the amount of memory actually used. In particular, for small examples such
as donald-* the increase in allocated memory just reflects the fact that an
additional memory block gets allocated.
19

Table 5: Event set experiments with priorities (allocated memory).
Example
bibd-7-3-60
crowded-chess-7
donald-b
donald-d
donald-v
golomb-10-b
golomb-10-d
minsort-200
partition-32
picture
queens-400
queens-400-a
average (above)
average (all)

no events
mem (KB)
6 690.1
198.2
7.8
3.4
5.8
39.7
37.7
32 419.1
160.3
451.6
30 286.6
567.0
—
—

only fix, dmc
mem
+2.9%
+4.0%
±0.0%
±0.0%
+34.3%
+2.6%
±0.0%
+1.1%
+3.7%
+17.7%
+0.2%
+2.8%
+5.4%
+3.9%

with bc
mem
+5.7%
+13.1%
+12.8%
+58.2%
+34.3%
+10.1%
+2.8%
+2.3%
+9.4%
+17.7%
+0.2%
+4.2%
+13.3%
+9.9%

with lbc, ubc
mem
+14.4%
+21.2%
+12.8%
+58.2%
+51.5%
+12.7%
+16.0%
+17.4%
+17.5%
+30.1%
+0.2%
+4.2%
+20.3%
+15.5%

Using just a fix event increases the required memory by less than 4% in
average, while using full event sets increases the required memory by 15.5% in
average.
It must be noted that Gecode (the system used) has a particularly efficient
implementation of event sets: the implementation uses a single pointer for an
entry in an event set; entries for the same variable and the same propagator
but with different events still use a single pointer. The memory overhead is due
to the fact that per variable and supported event, one single pointer for bookkeeping is needed. Hence, the highest overhead can be expected for examples
with many variables but relatively few propagators and small event sets (such
as bibd-7-3-60, crowded-chess-7, and picture). The overhead becomes less
noticeable for examples with many propagators or large event sets and few variables (such as queens-400 and queens-400-a).
Summary In summary, while there is a compelling argument for fix events,
there is only a weak case for bc being supported, and lbc and ubc should not
be used.

5.3

Dynamic Event Sets

Events help to improve the efficiency of a propagation-based solver. Just as we
can improve the use of fixpoint reasoning by examining the dynamic case, we
can also consider dynamically updating event sets as more information is known
about the variables in the propagator.
Monotonic event sets

20

Definition 5.8 [Monotonic propagator dependence] A propagator f is
monotonically dependent on a set of events es(f, D) in the context of domain D
iff
(a) for all domains D0 ⊑ D if f (D0 ) 6= f (f (D0 )) then events(D0 , f (D0 )) ∩
es(f, D) 6= ∅,
(b) for domains D0 and D1 where D0 ⊑ D, f (D0 ) = D0 , D1 ⊑ D0 and
f (D1 ) 6= D1 then events(D0 , D1 ) ∩ es(f, D) 6= ∅.
Clearly given this definition es(f, D) is monotonically decreasing with D.
The simplest kind of event reduction occurs by subsumption.
Definition 5.9 [Subsumption] A propagator f is subsumed for domain D, if
for each domain D′ ⊑ D we have f (D′ ) = D′ .
A subsumed propagator makes no future contribution. If f is subsumed
by D then es(f, D) = ∅ and f is never re-applied. Most current constraint
propagation systems take into account propagator subsumption.
Example 5.10 [Subsumption] Consider the propagator fA and the domain
D with D(x1 ) = [1 .. 3] and D(x2 ) = [3 .. 7]. Then the constraint holds for all
D′ ⊑ D and es(f, D) = ∅.
✷
Changing event sets can occur in cases other than subsumption.
Example 5.11 [Minimum propagator] Consider the propagator fK for x0 =
min(x1 , x2 ) defined by
fK (D)(x0 )
fK (D)(xi )
fK (D)(x)

= D(x0 ) ∩ [min(inf D x1 , inf D x2 ) .. min(supD x1 , supD x2 )]
= D(xi ) ∩ [inf D x0 .. + ∞]
i ∈ {1, 2}
= D(x)
x∈
6 {x0 , x1 , x2 }

The static event set es(fK ) is {lbc(x0 ), lbc(x1 ), ubc(x1 ), lbc(x2 ), ubc(x2 )}. Note
that this propagator is idempotent.
But given domain D where D(x0 ) = [1 .. 3] and D(x2 ) = [5 .. 7] we know that
modifying the value of x2 will never cause propagation. A minimal definition of
es(fK , D) is {lbc(x0 ), lbc(x1 ), ubc(x1 )}.
✷
Example 5.12 [exactly propagator] Another example is a propagator for
the exactly constraint [35]: exactly([x1 , . . . , xn ], m, k) states that exactly m
out of the variables x1 , . . . , xn are equal to a value k. As soon as one of the xi
becomes different from k, all events for xi can be ignored. Originally the events
are dmc(xi ), 1 ≤ i ≤ m, lbc(m), ubc(m) and dmc(k).
Suppose a domain D where D(k) = {1, 3, 8} and D(x3 ) = {2, 5, 6, 10, 11, 12},
then x3 6= k and we know its contribution to the exactly constraint. We can
remove the event dmc(x3 ) from the event set safely.
✷

21

Other examples for monotonic event sets are propagators for the lex constraint and the generalized element constraint. When using a variant of the lex
propagator proposed in [5], events can be removed as soon as the order among
pairs of variables being compared can be decided. For the generalized element
constraint [7] where the array elements are variables, events for a variable from
the array can be safely removed as soon as the variable becomes known to be
different from the result of the element constraint.
Using monotonic dynamic event sets we can refine our definition of new as
follows.
newmevents (f, F, D, D′ )
F ′ := {f ′ ∈ F | evset[f ′ ] ∩ events(D, D′ )} − fix(f, D)
evset[f ] := es(f, D′ )
return F ′
Every time a propagator f is applied its event set is updated to take into account
newly available information.
A related idea is the “type reduction” of [30] where propagators are improved as more knowledge on domains (here called types) becomes available.
For example, the implementation of x0 = x1 × x2 will be replaced by a more
efficient one, when all elements in D(x1 ) and D(x2 ) are non-negative. Here we
concentrate on how the event sets change. The two ideas could be merged as
they are complementary.
Proposition 5.13 newmevents maintains the invariant f (D) = D for all f ∈
F − Q at the start of the while loop.
Proof : The proof is almost identical to that for Proposition 5.7 since we are
working in a context if evset[f ] = es(f, D∗ ) then D ⊑ D∗ .
For propagators using the monotonic event sets, we have the invariant that
f ∈ F − Q iff evset[f ] = es(f, D∗ ) where D∗ is the result of the last time we
executed propagator f .
Suppose we have f ′ ∈ F − Q − {f } where f ′ (D′ ) 6= D′ and f (D) = D then
events(D∗ , D′ ) ∩ es(f, D∗ ) 6= ∅ and since f ′ 6∈ Q we have that events(D∗ , D) ∩
es(f, D∗ ) = ∅ otherwise we would have placed f in the queue already, hence by
the equation (1) events(D, D′ ) ∩ es(f, D∗ ) 6= ∅ so f ′ ∈ Q at the start of the loop.
Consider selected propagator f . Then it is removed from Q but if f (D′ ) 6= D′
then clearly fix(f, D) = ∅ and using case (a) of Definition 5.8 we have that
events(D, D′ ) ∩ es(f, D) 6= ∅. Hence f ∈ Q at the start of the loop. ✷
Fully dynamic event sets Note that for many propagators we can be more
aggressive in our definition of event sets if we allow the event sets to change in
a manner that is not necessarily monotonically decreasing.
Definition 5.14 [General propagator dependence] A propagator f is dependent on a set of events es(f, D) in the context of domain D if for all domains
D1 where D1 ⊏ D and f (D1 ) 6= D1 then events(D, D1 ) ∩ es(f, D) 6= ∅.
22

Using fully dynamic event sets we can refine our definition of new as follows.
newdevents (f, F, D, D′ )
F ′ := {f ′ ∈ F | evset[f ′ ] ∩ events(D, D′ )} − fix(f, D)
if (fix(f, D) = ∅)
F ′ := F ′ ∪ {f }
evset[f ] := es(f, D′ )
return F ′
Every time a propagator f is applied its event set is updated to take into
account newly available information. The only difficult case is that if the definition of dynamic dependency does not capture the events that occur when
moving from D to D′ = f (D). If fixpoint reasoning cannot guarantee a fixpoint
we need to add f to the queue.
Fully dynamic event sets are more powerful than monotonically decreasing
event sets, but in general they require reasoning about the new event sets each
time the propagator is run.
Example 5.15 [Fully dynamic events for minimum] Given the propagator
fK from Example 5.11 and the domain D where D(x0 ) = [0 .. 10], D(x1 ) =
[0 .. 15], and D(x2 ) = [5 .. 10]. D is a fixpoint of fK and a minimal set es(fK , D)
is
{lbc(x0 ), lbc(x1 ), ubc(x1 ), ubc(x2 )}
While at D′ ⊑ D where D′ (x0 ) = [5 .. 9], D′ (x1 ) = [6 .. 9], and D′ (x2 ) =
[5 .. 10], which is also a fixpoint, the minimal set es(fK , D′ ) is
{lbc(x0 ), ubc(x1 ), lbc(x2 ), ubc(x2 )}
For the constraint cK we simply need to maintain a lbc event for some
variable xi in the right hand side with the minimal lbc value.
✷
Proposition 5.16 newdevents maintains the invariant f (D) = D for all f ∈
F − Q at the start of the while loop.
Proof : We have the invariant that f ∈ F − Q iff evset[f ] = es(f, D∗ ) where D∗
is the result of the last time we executed propagator f .
Suppose we have f ′ ∈ F − Q − {f } where f ′ (D′ ) 6= D′ and f (D) = D then
events(D∗ , D′ ) ∩ es(f, D∗ ) 6= ∅ and since f ′ 6∈ Q we have that events(D∗ , D) ∩
es(f, D∗ ) = ∅ otherwise we would have placed f ′ in the queue already, hence
by the equation (1) events(D, D′ ) ∩ es(f, D∗ ) 6= ∅ so f ′ ∈ Q at the start of the
loop.
Consider the selected propagator f . The same reasoning cannot apply since
even though we know that events(D∗ , D′ ) ∩ es(f, D∗ ) 6= ∅, we have no guarantee
that events(D, D′ ) ∩ es(f, D∗ ) is not empty. Now if fix(f, D) = ∅ then possibly
f (D′ ) 6= D′ , but this will force f ∈ Q by the start of the loop. ✷
Effectively the fully dynamic event sets approach relies only on the dynamic
fixpoint reasoning of the propagator f to handle what happens when moving
from D to D′ .
23

Table 6: Dynamic event sets experiments (with priorities).
Example
bibd-7-3-60
crowded-chess-7
sequence-500
o-latin-7-d
average (above)
average (all)

time
+0.4%
−24.0%
−82.3%
−0.7%
−39.5%
−10.8%

monotonic
steps
mem
±0.0%
±0.0%
±0.0%
−15.2%
−78.3%
−49.5%
±0.0%
±0.0%
−31.8%
−19.1%
−8.2%
−4.1%

time
−5.0%
−28.2%
−82.1%
−1.7%
−41.1%
−11.2%

fully dynamic
steps
mem
−5.2%
±0.0%
−34.2%
−17.8%
−78.3%
−49.5%
±0.0%
±0.0%
−39.3%
−19.7%
−9.9%
−4.2%

Fully dynamic event sets are closely related to the watched literals approach
to improving unit propagation in SAT solving [25]. Using watched literals, unit
propagation only considers a clause for propagation if one of two watched literals
in the clause becomes false. Recently, the idea of watched literals has been used
in constraint programming for the Minion solver [13]. Watched literals differ
from the events we concentrate on here since they take into account values
(similar to the neq(x, a) event). Note that dynamic event sets do not usually
have the property of watched literals, in that they do not need to be updated
on backtracking.

5.4

Dynamic Event Sets Experiments

Table 6 shows the comparison of monotonic and fully dynamic event sets to a
propagation solver using static event sets with {fix, bc, dmc} events and priorities to avoid priority inversion as discussed before. The table lists only examples
where dynamic event sets are used.
The propagators using monotonic event sets are as follows: for bibd-7-3-60:
lex; for crowded-chess-7: exactly and element; for sequence-500: exactly;
for o-latin-7-d: lex. Clearly, monotonic event sets lead to a drastic reduction
in both runtime and memory usage, where it is worth noting that the reduction
in time is even more marked than the reduction in propagation steps (each
propagation step becomes cheaper as smaller event sets must be maintained).
Fully dynamic event sets are considered in Boolean-sum propagators used in
bibd-7-3-60 and crowded-chess-7. The difference in improvement between
the two examples can be explained by the fact that crowded-chess-7 uses
Boolean-sums as inequalities while bibd-7-3-60 uses Boolean-sums as equalities
where inequalities offer the potential for considerably smaller event sets [13].
Example bibd-7-3-60 provides another insight: the drastic reduction in
runtime observed in [13] by using watched literals for Boolean-sum propagators
in the Minion solver is most likely not due to small event sets but to other
aspects. A possible aspect is the knowledge about which variables have been
modified when a propagator is executed.

24

Table 7: Queue versus stack experiments.
Example
all-interval-500
alpha
bibd-7-3-60
cars
crowded-chess-7
donald-b
donald-d
donald-v
golomb-10-b
golomb-10-d
graph-color
grocery
knights-10
minsort-200
o-latin-7-d
partition-32
photo
picture
queens-400
queens-400-a
sequence-500
square-5-d
square-7-b
square-7-v
warehouse
average (all)

6

queue
time (ms)
steps
73.00
377 777
97.31
207 470
2 020.30
1 020 162
4.65
14 860
553.25
660 525
0.62
414
28.53
40
0.36
366
1 342.48
2 095 161
3 201.84
2 091 691
33.54
4 422
56.87
2 211
6.66
25 225
141.84
113 437
532.48
311 135
9 001.24
13 939 101
90.37
296 661
1 583.12
119 406
549.36
268 771
14.40
1 265
98.12
56 048
32 263.12
1 478 403
9 491.84
6 054 656
5 345.00
9 636 675
0.70
2 075
—
—

stack
time
steps
+13626.0%
+32.2%
+47.5%
+99.0%
+7.7%
+102.7%
+1.3%
+2.6%
+4.7%
+68.1%
+36.3%
+31.9%
−5.4%
+7.5%
+7.6%
+23.2%
+870.6%
+171.5%
−11.9%
+98.9%
+299.7%
+118.4%
+44.2%
−6.3%
+7.7%
+53.3%
+1580.1%
+1123.3%
+4.9%
+24.9%
−18.5%
+34.8%
+11.1%
+8.7%
+27.1%
+79.9%
±0.0%
−0.1%
−0.9%
−0.3%
+53.8%
+240.9%
+71.5%
+57.7%
+75.3%
+44.9%
+8.3%
+35.2%
+11.7%
+29.3%
+78.4%
+61.0%

Which Propagator to Execute Next

We now address how to define which propagator f in the queue Q should execute
first, that is how to define the choose function.
The simplest policy to implement is a FIFO (First In First Out) queue
of propagators. Propagators are added to the queue, if they are not already
present, and choose selects the oldest propagator in the queue. The FIFO
policy ensures fairness so that computation is not dominated by a single group
of propagators, while possibly not discovering failure (a false domain) from other
propagators quickly.
The equally simple LIFO (Last In First Out) policy is a stack where propagators not already in the stack are pushed, and choose selects the top of the
stack.

25

6.1

Basic Queuing Strategy Experiments

Table 7 compares using a FIFO queue versus a LIFO stack. The result, according with folklore knowledge, clearly illustrates that a queue must be used. The
few cases where a stack is better are comprehensively outweighed by the worst
cases for a stack.
Later experiments in Section 6.3 using priorities with combinations of FIFO
queues and LIFO stacks reveal that the pathological behavior of all-interval-500
is due to priority inversion. However, the pathological behavior of minsort-200
is due to the use of a LIFO stack.

6.2

Static Priorities

A statically prioritized queue associates with each propagator a fixed priority,
we will assume an integer in the range [0 .. k − 1]. In effect, the queue Q is
split into k queues, Q[0], . . . Q[k − 1] where each Q[i] is a FIFO queue for the
propagators with priority i. Selection always chooses the oldest propagator in
the lowest numbered queue Q[i] that is non-empty. Static prioritization allows
one to ensure that quick propagators are executed before slow propagators.
We give an example of seven static priorities, with names of the integer priorities as follows: unary=0, binary=1, ternary=2, linear=3, quadratic=4,
cubic=5, and veryslow=6. The names are meant to represent the arity of the
constraint, and then the asymptotic runtime of the propagator, once the constraint can handle n variables. So binary is for binary constraints, quadratic
is for constraints that are approximately O(n2 ) for instances with n variables.
Example 6.1 [Propagator priorities] For example, the propagator fL for
even(x1 ) defined by


fL (D)(x1 ) = D(x1 ) ∩ 2⌈ 21 inf D x1 ⌉ .. 2⌊ 21 supD (x1 )⌋
fL (D)(x) = D(x)
x 6= x1
might be given priority unary, while fE and fF might be given priority binary.
The domain propagator defined in [29] for the alldifferent constraint
∧ni=1 ∧nj=i+1 xi 6= xj (with complexity O(n2.5 )) might be given priority quadratic.
The alldifferent bounds(Z) propagator defined in [28] (with complexity
O(n log n)) might be given priority linear.
✷
Priorities in effect force many more fixpoints to be calculated. A fixpoint of
all propagators at priority level i and lower must be reached before a propagator
at priority level i + 1 is run. This means we will often cause more propagators
to run when using priorities, but more cheap propagators!
Example 6.2 [Repeated fixpoints] Consider the execution of a system of
propagators for constraints cC ≡ x1 = 2x2 , cD ≡ x1 = 3x2 , cM ≡ x2 ≤
6 → x1 ≤ x3 + 7 and cN ≡ alldifferent[x1 , x2 , x3 , x4 , x5 ]. We will use the
bounds(R) propagators fC , fD , fM for the first three constraints, and the domain propagator, fN , for alldifferent from [29], for the last constraint. Let
26

the initial domain be D(x1 ) = [0 .. 18], D(x2 ) = [0 .. 9], D(x3 ) = [0 .. 6], and
D(x4 ) = D(x5 ) = [0 .. 3]. The priorities are binary, binary, ternary, and
quadratic respectively. All propagators are at fixpoint.
Suppose the domain of x1 changes to [0 .. 17]. All propagators are enqued.
The priority level binary propagators are run to fixpoint (as in Example 3.2)
giving D(x1 ) = [0 .. 12], D(x2 ) = [0 .. 6], D(x3 ) = [0 .. 4] Then fM is scheduled and causes D(x1 ) = [0 .. 11]. Both fC and fD are enqued, and after
executing fC , fD , fC and fD the next fixpoint of the binary priority propagators is reached: D(x1 ) = [0 .. 6], D(x2 ) = [0 .. 3], D(x3 ) = [0 .. 2]. Then
fM is scheduled again and causes no change. After that, fN is executed, it
reduces the domains of D(x1 ) = [4 .. 6] since all the values [0 .. 3] are required
for the variables x2 , x3 , x4 , x5 . Both fC and fD are enqued, and after executing we reach their fixpoint D(x1 ) = {6}, D(x2 ) = {3}, D(x3 ) = {2}. Once
again fM is executed for no change. Then fN is executed once more obtaining
D(x4 ) = D(x5 ) = {0, 1}. This is the overall fixpoint.
✷
We can adjust the granularity of the priorities: we can have a finer version
of the above priorities with 14 priorities, each priority above with a low and
high version. This allows us to separate, for example, a domain consistent
propagator for the binary absolute value constraint abs(x) = y (binary-low)
from a bounds consistent propagator for the same constraint (binary-high).
This increased granularity will be important in Section 7.
Conversely, we may collapse the priorities into fewer levels, for example into
three levels unary-ternary, linear-quadratic, cubic-veryslow.
Another model for priorities in constraint propagation based on composition
operators is [14]. The model, however, runs all propagators of lower priority
before switching propagation back to propagators of higher priority. This model
does not preempt computing a fixpoint for a low priority. The model always
completes a fixpoint for a given priority level and only then possibly continues
at a higher priority level.
Most systems have some form of static priorities, typically using two priority
levels (for example, SICStus [18], Mozart [26]). The two levels are often not
entirely based on cost: in SICStus all indexicals have high priority and all other
lower priority. While ECLi PSe [36, 15] supports twelve priority levels, its finite
domain solver also uses only two priority levels where another level is used to
support constraint debugging.
A similar, but more powerful approach is used by Choco [19] using seven
priority levels allowing both LIFO and FIFO traversal.
Prioritizing particular operations during constraint propagation is important
in general.
For interval narrowing, prioritizing constraints can avoid slow
convergence, see for example [20].
The prioritizing of propagators by cost is important, inverting the priorities
can lead to significant disadvantages.
Example 6.3 [Inverted priorities] Consider executing Example 6.2 with inverted priorities. We first execute fN then fM for no effect. Then executing fC
27

Table 8: Priority experiments with varying granularities.
Example
all-interval-500
alpha
bibd-7-3-60
cars
crowded-chess-7
donald-b
donald-d
donald-v
golomb-10-b
golomb-10-d
graph-color
grocery
knights-10
minsort-200
o-latin-7-d
partition-32
photo
picture
queens-400
queens-400-a
sequence-500
square-5-d
square-7-b
square-7-v
warehouse
average (all)

small
time
steps
+1.8%
+0.3%
+1.2%
±0.0%
+0.1%
+16.9%
−1.4%
−10.4%
+8.1%
+91.2%
+1.1%
±0.0%
−0.1%
±0.0%
+1.6%
±0.0%
−33.1%
+33.5%
−49.5%
+29.2%
−1.3%
±0.0%
+10.3%
−9.2%
−3.4%
−19.5%
+0.5%
±0.0%
−10.6%
+4.6%
−38.6%
−18.2%
+0.1%
+3.4%
−1.0%
±0.0%
+0.7%
±0.0%
+0.2%
±0.0%
+0.5%
±0.0%
−0.5%
±0.0%
+1.3%
±0.0%
+0.9%
±0.0%
+5.3%
+13.0%
−5.6%
+3.8%

medium
time
steps
+2.3%
+0.3%
+1.2%
±0.0%
+0.1% +16.9%
−1.5% −10.5%
+9.0% +91.2%
+0.4%
±0.0%
−5.6%
+5.0%
+2.6%
±0.0%
−31.3%
+51.0%
−49.0%
+46.7%
−1.3%
−0.1%
−5.6%
+1.9%
−4.7% −19.9%
+0.5%
±0.0%
−11.0%
+4.6%
−38.7%
−17.8%
+0.2%
+3.4%
−1.5%
±0.0%
+0.5%
±0.0%
+0.2%
±0.0%
+0.3%
±0.0%
+0.9% +23.8%
+0.4%
±0.0%
+0.7%
±0.0%
+5.7% +12.0%
−6.3%
+6.4%

full
time
+2.3%
+1.2%
+0.2%
−1.8%
+8.8%
+0.9%
−5.5%
+2.2%
−31.6%
−48.9%
−0.9%
−5.6%
−3.7%
−0.2%
−10.6%
−38.4%
−7.3%
+0.2%
+0.5%
+0.3%
+0.6%
+1.1%
−23.4%
+0.9%
+5.3%
−7.4%

steps
+0.3%
±0.0%
+16.9%
−10.5%
+91.1%
±0.0%
+5.0%
±0.0%
+51.0%
+46.7%
−0.1%
+1.9%
−19.9%
±0.0%
+4.6%
−17.8%
−1.8%
±0.0%
±0.0%
±0.0%
±0.0%
+23.8%
+22.0%
±0.0%
+12.0%
+7.0%

modifies D(x1 ), so each of fN and fM are enqued and re-executed for no effect.
Then executing fD has the same behavior. Overall we execute the propagators
fM and fN each at least 10 times, as opposed to 3 and 2 times respectively in
Example 6.2. Since they are the most expensive to execute we would expect
this to be slower (this is confirmed immediately below).
✷

6.3

Static Priority Experiments

Priority granularity Table 8 gives runtime and propagation steps of various
priority granularities compared to a propagation engine using a FIFO queue (and
using dynamic fixpoint reasoning, events of types {fix, bc, dmc}, and fully dynamic event sets). The three different experiment capture different priority granularities: “small” uses three priorities (unary-ternary, linear-quadratic,
cubic-veryslow); “medium” uses seven priority levels (from unary to veryslow);
“full” uses 14 priority levels (from unary-high to veryslow-low).
The results illustrate that even when there are substantially more propagations (for example, golomb-10-{b,d}) there can be significant savings. Priori-

28

ties can have a very substantial saving (almost 50% for golomb-10-d) and the
worst case cost on the benchmarks is only 10.3%. Overall while the “medium”
range of priorities is preferable on many benchmarks, the “full” range of priorities gives real speedups on two more benchmarks (photo and square-7-b) and
tends to reduce the worst case behavior of “medium”.
Examples such as queens-400, queens-400-a, and sequence-500 for “small”
only feature propagators with the same priority (the number of propagation
steps remains the same). Hence the increase in runtime by less than 1% describes the overhead of using priorities at all.
Depending on the underlying system, increasing the granularity also requires
more memory. Gecode, as a system based on recomputation and copying, constitutes the worst case in that each copied node in the search tree maintains
queues for all priority levels. However, the average increase in used (not allocated as before) memory is +0.2% for “small”, +0.7% for “medium”, and +1.5%
for “full” and hence can be neglected.
A broad spectrum of priorities will be useful for the optimizations presented
in Section 7. Therefore it is important that while “full” does not offer huge
advantages over “medium”, it neither degrades overall performance nor requires
much memory.
Priorities and stacks Table 9 gives the runtime and propagation steps of
using priorities together with stacks or combinations of stacks and queues for
the different priority levels. All numbers are given relative to a propagation
engine using the “full” priority spectrum with only queues for each priority
level. All propagation engines considered also use the full priority spectrum. The
propagation engine for “for all” uses only stacks for all priority levels, whereas
“for 1, 2, 3-ary” (“for 1, 2-ary”) uses stacks for priority levels unary-high to
ternary-low (unary-high to binary-low) and queues for the other levels.
The numbers for “for all” clarify that the misbehavior of LIFO stacks is
not due to priority inversion. The folklore belief that LIFO stacks are good
for small propagators is refuted by the numbers for “for 1, 2, 3-ary” and “for
1, 2-ary”. Only three examples show improvement in both cases while grocery
“for 1, 2, 3-ary” already exhibits pathological behavior. The measurements show
that queue versus stack does not matter for unary or binary constraints whereas
stacks are wrong for anything else.
Issues to avoid Table 10 shows runtime and propagation steps of using priorities in flawed ways. The experiment “complete fixpoints” refers to the model
proposed in [14] where fixpoints are always completed before possibly switching
to a higher priority level. As to be expected, the number of propagation steps
is reduced, however at the expense of increased runtime. More importantly,
two examples exhibiting substantial slowdown (golomb-10-d and square-5-d)
are particularly relevant as they feature propagators of vastly different priority
levels.
The surprising behavior of bibd-7-3-60 appears to be due to a problem

29

Table 9: Priority experiments with stacks and priorities.
Example
all-interval-500
alpha
bibd-7-3-60
cars
crowded-chess-7
donald-b
donald-d
donald-v
golomb-10-b
golomb-10-d
graph-color
grocery
knights-10
minsort-200
o-latin-7-d
partition-32
photo
picture
queens-400
queens-400-a
sequence-500
square-5-d
square-7-b
square-7-v
warehouse
average (all)

for all
time
steps
−0.6%
±0.0%
+47.2%
+99.0%
+5.5%
+49.7%
−4.2%
−7.3%
+0.6%
+10.4%
+0.3%
±0.0%
−0.6%
+2.4%
+7.7%
+23.2%
+7.1%
+27.0%
+5.7%
+39.2%
+62.7%
+77.1%
+42.8%
+7.1%
+0.1%
+5.0%
+1545.4%
+1106.4%
−3.3%
+5.2%
−2.2%
−2.9%
−1.3%
−0.8%
+21.1%
+79.9%
−0.1%
−0.1%
−1.0%
−0.3%
+54.1%
+240.9%
+65.2%
+31.6%
+1.7%
+18.6%
+8.9%
+35.2%
−2.5%
+1.7%
+23.9%
+36.0%

30

for 1, 2, 3-ary
time
steps
+1.3%
±0.0%
+2.3%
±0.0%
−4.0%
+1.4%
+1.2%
−2.0%
+2.0%
±0.0%
+1.6%
±0.0%
+1.0%
±0.0%
+2.5%
±0.0%
+9.7%
+27.0%
+7.7%
+39.2%
+2.3%
±0.0%
+45.8%
+7.1%
+2.1%
+5.0%
+2.2%
±0.0%
+1.0%
+0.3%
+2.2%
+2.3%
−1.0%
−0.9%
−1.3%
±0.0%
+1.0%
−0.1%
+1.2%
±0.0%
+1.4%
±0.0%
+1.2%
±0.0%
+1.4%
±0.0%
+2.9%
±0.0%
+3.0%
+0.2%
+3.3%
+2.8%

for 1, 2-ary
time
steps
+0.2% ±0.0%
+1.0% ±0.0%
−5.9% +1.4%
+1.8% −2.0%
+1.7% ±0.0%
+0.9% ±0.0%
+0.3% ±0.0%
+1.7% ±0.0%
+1.2% ±0.0%
+1.0% ±0.0%
+1.5% ±0.0%
+1.6% −0.3%
+1.4% +5.0%
+2.4% ±0.0%
−0.4% +0.3%
+2.2% +0.4%
+0.1% −0.9%
−1.2% ±0.0%
+0.8% −0.1%
+1.2% ±0.0%
+0.8% ±0.0%
+0.8% ±0.0%
+0.8% ±0.0%
+2.6% ±0.0%
+3.0% +0.2%
+0.8% +0.2%

Table 10: Priority experiments: issues to avoid.
Example
all-interval-500
alpha
bibd-7-3-60
cars
crowded-chess-7
donald-b
donald-d
donald-v
golomb-10-b
golomb-10-d
graph-color
grocery
knights-10
minsort-200
o-latin-7-d
partition-32
photo
picture
queens-400
queens-400-a
sequence-500
square-5-d
square-7-b
square-7-v
warehouse
average (all)

complete
time
−0.8%
+0.5%
−11.7%
−1.2%
−4.2%
+0.9%
+0.9%
+1.6%
−2.5%
+14.6%
+1.9%
+29.3%
−0.9%
+5.5%
+7.3%
+0.4%
+1.2%
−3.6%
−0.7%
+0.3%
+0.2%
+32.5%
+0.5%
+2.6%
−3.7%
+2.5%

fixpoints
steps
±0.0%
±0.0%
−45.8%
−0.9%
−41.1%
±0.0%
±0.0%
±0.0%
−14.5%
−14.2%
+0.1%
−23.4%
±0.0%
+8.6%
−3.8%
−1.2%
±0.0%
±0.0%
±0.0%
±0.0%
±0.0%
+7.9%
±0.0%
±0.0%
−9.0%
−6.6%

31

inverse priorities
time
steps
+13296.5%
+32.1%
+0.3%
±0.0%
−7.7%
−42.8%
+14.4%
+40.1%
−7.4%
−52.0%
+36.8%
+31.9%
+6.2%
−7.1%
+0.2%
±0.0%
+892.0%
−5.7%
+945.4%
−2.2%
+336.8%
+51.1%
+35.3%
+9.1%
+8.7%
+43.5%
+2732.2%
+2246.7%
+105.1%
+18.7%
+108.3%
+66.8%
+18.6%
−1.9%
−3.7%
±0.0%
+0.2%
±0.0%
−0.3%
±0.0%
−0.2%
±0.0%
+50.1%
+7.5%
+177.4%
−7.6%
±0.0%
±0.0%
+14.7%
+11.3%
+107.5%
+18.4%

with how the priorities for the two different kinds of propagators used in this
example (lex and Boolean-sum) are classified. This clarifies that even with a
rich spectrum of priority levels at disposal it remains difficult to assign priority
levels to propagators.
The experiment “inverse priorities” shows numbers for a propagation engine
where a propagator with lowest priority is executed first. The experiment shows
that there is a point to the priority levels, high priority = fast propagator. While
the number of propagations is often reduced the approach is rarely better than
no priorities and sometimes catastrophically worse.
The experiment “inverse priorities” clarifies a very important aspect of priorities: they not only serve as a means to improve performance, they also serve
as a safeguard against pathological propagation order.

6.4

Dynamic Priorities

As evaluation proceeds, variables become fixed and propagators can be replaced
by more specialized versions. If a propagator is replaced by a more specialized
version, also its priority should change.
Example 6.4 [Updating a propagator] Consider the propagator fO for updating x1 in the constraint x1 = x2 + x3 defined by
fO (D)(x1 ) =
fO (D)(x) =

D(x1 ) ∩ [inf D (x2 ) + inf D (x3 ) .. supD (x2 ) + supD (x3 )]
D(x)

x 6= x1

might have initial priority ternary. When the variable x2 becomes fixed to d2
say, then the implementation for x1 can change to
fO (D)(x1 ) = D(x1 ) ∩ [d2 + inf D (x3 ) .. d2 + supD (x3 )]
and the priority can change to binary.

✷

Changing priorities is also relevant when a propagator with n > 3 variables
with priority linear (or worse) reduces to a binary or ternary propagator.

6.5

Dynamic Priority Experiments

Table 11 shows runtime and propagation steps for an engine using dynamic
priorities compared to an engine using all optimizations introduced earlier and
the full priority spectrum. Dynamically changing the priority of propagators as
they become smaller due to fixed variables can lead to significant improvements.
In effect, constraints that become smaller (and thus run at higher priority) are
run first causing the still large constraints to be run less often.
This is in particular true for alpha with initially only propagators for linear equalities with priority linear. When fixing variables during search many
of these propagators are then run at priority levels binary and ternary. It
is worth noting that using dynamic priorities can disturb the FIFO queue behavior: for sequence-500 it appears to be more important to run all exactly
32

Table 11: Dynamic priority experiments.
Example
alpha
cars
crowded-chess-7
o-latin-7-d
picture
sequence-500
average (above)
average (all)

dynamic
time
steps
−25.5% −41.7%
−5.9% −13.4%
−5.0% −26.5%
−7.3%
−7.4%
−1.9%
±0.0%
+6.0% +34.8%
−7.1% −12.1%
−1.7%
−3.0%

propagators at the same priority level. Running some of the exactly propagators at priorities binary and ternary is not beneficial and disturbs the queue
behavior.
Dynamic priorities incur the overhead to compute the priority based on the
number of not yet fixed variables. However, the overhead is still small enough
to make dynamic priorities worthwhile overall.

7

Combining Propagation

There are many ways to define a correct propagator f for a single constraint
c: the art of building propagators is to find good tradeoffs in terms of speed
of execution versus strength of propagation. Typically a single constraint may
have a number of different propagator implementations: the cheapest simple
propagator, a more complex bounds propagator, and a more complex domain
propagator, for example.
Example 7.1 [alldifferent propagators] Consider the propagator fP (D)
for the alldifferent constraint.
E := ∅
for i ∈ [1 .. n]
if (∃d.D(xi ) = {d})
if (d ∈ E) return D⊥ else E := E ∪ {d}
for i ∈ [1 .. n]
if (|D(xi )| > 1) D(xi ) := D(xi ) − E
return D
The propagator does a linear number of set operations in each invocation and is
checking. It can be made idempotent by testing that no variable becomes fixed.
Another propagator for the same constraint is the domain propagator fN
introduced in [29] with complexity O(n2.5 ).
✷

33

Given two propagators, say f1 and f2 in prop(c), where f1 is strictly stronger
than f2 (f1 (D) ⊑ f2 (D) for all domains D), we could choose to implement c by
just f1 or just f2 trading off pruning versus execution time.
Without priorities there is no point in implementing the constraint c using
both propagators, since f1 will always be run and always compute stronger
domains than f2 .
We could possibly merge the implementation of the propagators to create
a new propagator f12 (D) = f1 (f2 (D)). By running the cheaper propagator
immediately first we hope that we can (a) quickly determine failure in some cases
and (b) simplify the domains before applying the more complicated propagator
f1 . While this immediate combination of two propagators in essence is simply
building a new propagator, once we have priorities in our propagation engine
we can use two or more propagators for the same constraint in different ways.

7.1

Multiple Propagators

Once we have priorities it makes sense to use multiple propagators to implement
the same constraint. We can run the weaker (and presumably faster) propagator
f2 with a higher priority than f1 . This makes information available earlier to
other propagators. When the stronger propagator f1 is eventually run, it is able
to take advantage from propagation provided by other cheaper propagators.
Note that this is essentially different from having a single propagator f12
that always first runs the algorithm of f2 and then the algorithm of f1 .
Example 7.2 [Multiple alldifferent] Consider the two propagators fP and
fN defined in Example 7.1 above. We can use both propagators: fP with priority
linear, and fN with priority quadratic. This means that we will not invoke
fN until we have reached a fixpoint of fP and all linear and higher priority
propagators.
Consider the additional propagator fE for the constraint 3x1 = 2x2 , which
has priority binary. Consider the domain D where D(x1 ) = {4, 6}, D(x2 ) =
{6, 9}, D(x3 ) = {6, 7} and D(x4 ) = · · · = D(xn ) = [1 .. n], which is a fixpoint
for fE , fP and fN . Now assume the domain of x3 is reduced to 6. Propagator
fP is placed in queue linear and fN is placed in queue quadratic. Applying
fP removes 6 from the domain of all the domains of x1 , x2 , x4 , . . . , xn , and this
causes fE to be placed in queue binary. This is the next propagator considered
and it causes failure. Propagator fN is never executed.
If we just use fN then we need to invoke the more expensive fN to obtain
the same domain changes as fP , and then fail.
✷

7.2

Staged Propagators

Once we are willing to use multiple propagators for a single constraint it becomes
worth considering how to more efficiently manage them. Instead of using two
(or more) distinct propagators we can combine the several propagators into a
single propagator with more effective behavior.

34

We assume that a propagator has an internal state variable, called its stage.
When it is invoked, the stage determines what form of propagation applies.
Example 7.3 [Staged alldifferent] Consider the alldifferent constraint
with implementations fP and fN discussed in Example 7.1. We combine them
into a staged propagator as follows:
• On a fix(x) event, the propagator is moved to stage A, and placed in the
queue with priority linear.
• On a dmc(x) event, unless the propagator is in stage A already, the propagator is put in stage B, and placed in the queue with priority quadratic.
• Execution in stage A uses fP , the propagator is put in stage B, and placed
in the queue with priority quadratic, unless it is subsumed.
• Execution in stage B uses fN , afterwards the propagator is removed from
all queues (stage NONE).
The behavior of the staged propagator is identical to the multiple propagators for the sample execution of Example 7.1. In addition to the obvious
advantage of having a single staged propagator, another advantage comes from
avoiding the execution of fN when the constraint is subsumed.
✷
In addition to giving other propagators with higher priority the opportunity
to run before the expensive part of a staged propagator, the first stage of a
propagator can already determine that the next second does not need to be
run. This is illustrated by the following example.
Example 7.4 [Staged linear equations] Consider the unit coefficient linear
equation Σni=1 ai xi = d constraint where |ai | = 1, 1 ≤ i ≤ n. We have two implementations, fQ , which implements bounds(R) consistency (considering real
solutions, with linear complexity) for the constraint, and fR , which implements
domain consistency (with exponential complexity).
We combine them into a staged propagator as follows:
• On a bc(x) (or depending on the event types available: lbc(x) or ubc(x))
event, the propagator is moved to stage A, and placed in the queue with
priority linear.
• On a dmc(x) event, unless the propagator is in stage A already, the propagator is put in stage B, and is placed in the queue with priority veryslow.
• Execution in stage A uses fQ , afterwards the propagator is put in stage B,
and placed in the queue with priority veryslow, unless each xi has a range
domain in which case it is removed from all queues (stage NONE).
• Execution in stage B uses fR , afterwards the propagator is removed from
all queues (stage NONE).

35

Table 12: Combination experiments.
Example
donald-b
donald-d
golomb-10-b
golomb-10-d
graph-color
o-latin-7-d
partition-32
photo
picture
square-5-d
square-7-b
average (above)
average (all)

immediate
time
steps
+0.7% ±0.0%
−1.6% −2.4%
+0.3% ±0.0%
−2.7% +0.2%
−0.6% −0.6%
−1.2% +1.0%
−0.6% ±0.0%
±0.0% ±0.0%
+0.3% ±0.0%
−29.6% −7.4%
−0.1% ±0.0%
−3.6% −0.9%
−1.6% −0.4%

multiple
time
steps
−15.4%
+10.4%
±0.0%
+111.9%
−10.1%
+9.2%
−14.5%
+8.6%
+2.0%
+23.0%
−9.6%
+14.3%
−4.3%
+7.4%
−0.9%
+7.8%
−0.1%
±0.0%
−38.3%
+28.8%
−17.5%
−11.0%
−10.7%
+16.1%
−4.8%
+6.8%

staged
time
steps
−16.9% +10.1%
−1.6% +88.1%
−9.8%
+9.2%
−16.1%
+8.6%
−14.4% +12.3%
−14.0% +10.9%
−6.2%
+4.2%
−1.5%
+7.8%
−3.4%
±0.0%
−42.8% +56.0%
−18.6% −10.9%
−14.0% +15.3%
−6.5%
+6.5%

The staged propagator is advantageous since the “fast” propagator fQ can
more often determine that its result D′ = fQ (D) is also a fixpoint for fR .
✷
Staged propagators are widely applicable. They can be used similarly for the
bounds(Z) version of the alldifferent constraint. Another area where staged
propagators can be used is constraint-based scheduling, where typically different
propagation methods with different strength and efficiency are available [2].
Staging is not limited to expensive propagators, it is already useful for binary
(for example, combining bounds and domain propagation for the absolute value
constraint abs(x) = y) and ternary constraints (for example, combining bounds
and domain propagation for the multiplication constraint x × y = z).
It is important to note that staging requires a sufficiently rich spectrum of
priorities. For example, to use staging for binary or ternary propagators as mentioned above, at least two different priority levels must be available for staging.
This explains why the full priority spectrum is useful: here, for binary propagators two priorities binary-high and binary-low are available. Likewise,
ternary-high and ternary-low are available for ternary propagators.

7.3

Combining Propagation Experiments

Table 12 presents runtime and propagation steps of different propagator combination schemes compared to a propagation engine using the full priority spectrum and all optimizations presented so far. The experiment “immediate” uses
a single propagator that always runs the first stage immediately followed by
the second stage. For experiment “multiple”, multiple propagators for different
stages (as discussed in Section 7.1) are used, whereas for experiment “staged”
full staging is used (as described in Section 7.2).
A quite surprising result is that “immediate” offers only modest or even

36

no speedup. The only exception is square-5-d using bounds(R) propagation
immediately before domain propagation for several linear equation propagators.
Using multiple propagators leads to an average reduction in runtime by 10%
with a slowdown for just a single example (graph-color). As to be expected,
the number of propagation steps rises sharply. This is due to the fact that more
propagators need to be run and that, similar to the introduction of priorities,
propagators with high priority are run more often. The exceptional case of
square-7-b where the number of propagation steps decreases appears to be a
fortunate change in propagation order.
Staged propagation offers another level of improvement over using multiple
propagators: all examples now achieve speedup. As fewer propagators must
be executed compared to “multiple”, also the number of propagation steps decreases (apart from square-5-d being another case of changing propagation
order). Due to the reduced overhead compared to “multiple”, even small examples such as graph-color are able to benefit from staged execution.
The exact improvement in runtime of donald-d for “immediate” and “staged”
is due to early fixpoint detection for a big linear equation propagator as discussed in Example 7.4.
The memory requirements for “immediate” and “staged” are unchanged.
The use of multiple propagators for “multiple” leads to an average increase of
6.4% in allocated memory for the examples shown in Table 12.
In summary, staged propagation is very effective for all examples, so it should
clearly be used.

8

Experiment Summary

In Table 13 we summarize the effect of all improvements suggested in this paper.
The naive propagation engine is compared to an engine featuring all techniques
introduced in this paper: dynamic fixpoint reasoning, {dmc, fix, bc} fully dynamic events, dynamic priority based LIFO queuing with the full priority spectrum, and staged propagators.
It is interesting to note that all examples but warehouse show an improvement in runtime and that almost 75% of the examples show an improvement
of at least 10%. The improvement in runtime does not incur a large increase
in memory: the largest increases are for the three donald-* problems, where
the increase is actually negligible in absolute terms and due to the underlying
memory allocation strategy (as discussed in Section 5.2).
The effects of the individual optimizations discussed in this paper could be
summarized as follows. Dynamic fixpoint reasoning subsumes static reasoning
and is easy to implement, it provides a modest improvement in execution times.
Events, while used in all finite domain propagation engines, have less benefit
than perhaps was assumed by developers. Using dynamic events again leads to a
modest improvement in execution times. The fairness of a FIFO queue strategy
is essential for scheduling propagators. While priorities by themselves are not
that important they provide a protection against worst case behavior and enable

37

Table 13: Experiment summary.
Example
all-interval-500
alpha
bibd-7-3-60
cars
crowded-chess-7
donald-b
donald-d
donald-v
golomb-10-b
golomb-10-d
graph-color
grocery
knights-10
minsort-200
o-latin-7-d
partition-32
photo
picture
queens-400
queens-400-a
sequence-500
square-5-d
square-7-b
square-7-v
warehouse
average (all)

no optimizations
time (ms) mem (KB)
118.31
385.4
106.56
22.2
2 279.36
6 688.6
4.64
41.7
624.25
196.9
0.70
7.4
30.37
3.2
0.38
5.4
1 347.48
40.0
2 430.00
37.0
35.87
832.4
55.41
7.7
7.46
770.3
342.48
32 454.5
574.36
242.9
8 571.24
160.4
108.87
37.0
1 553.42
450.5
4 433.12
30 286.1
16.15
566.3
517.96
6 081.5
33 391.24
43.5
10 166.24
160.3
5 690.00
144.2
0.74
29.4
—
—

38

all optimizations
time
memory
−36.1%
+25.0%
−31.2%
+9.8%
−11.0%
+5.8%
−7.7%
+1.2%
−8.1%
−6.4%
−25.7%
+19.0%
−13.0%
+68.2%
−3.3%
+44.4%
−38.5%
+9.3%
−43.7%
+4.8%
−19.9%
+9.0%
−5.9%
+7.9%
−14.7%
+4.2%
−58.8%
−5.1%
−32.5%
+5.5%
−40.4%
+9.2%
−23.8%
+10.1%
−3.0%
+18.0%
−87.6%
+0.2%
−10.3%
+4.4%
−79.8%
−49.4%
−44.2%
+11.9%
−41.2%
+8.7%
−3.9%
+11.7%
+1.2%
+1.0%
−33.3%
+7.2%

the use of multiple propagators. Staging is an important optimization that can
significantly improve performance.

9

Conclusion and Future Work

We have given a formal definition of propagation systems including idempotence,
events, and priorities used in current propagation systems and have evaluated
their impact. We have introduced dynamically changing event sets which are
shown to improve efficiency considerably. The paper has introduced multiple
and staged propagators which are shown to be an important optimization in
particular for improving the efficiency of costly global constraints.
While the improvements to an engine of a propagation based constraint
solver have been discussed for integer constraints, the techniques readily carry
over to arbitrary constraint domains such as finite sets and multisets.
A rather obvious way to further speed up constraint propagation is to consider not only cost but also estimated impact for a propagator. However, while
computing cost is straightforward it is currently not clear to us how to accurately
predict propagation impact.

A

Examples Used in Experiments

All variants of constraint propagation discussed in the paper are experimentally
evaluated. The characteristics of the examples used in evaluation are summarized in Table 14. The column “variables” gives the number of variables in the
example, whereas the column “propagators” shows the number of propagators
as implementations of constraints in the example. The column “search” shows
which search strategy is used to search for a solution (“first” is simple backtracking search for the first solution, “all” is search for all solutions, “best” is
branch-and-bound search for a best solution). The two last columns describe
how many failed nodes are explored during search (column “failures”) and how
many solutions are found (column “solutions”).
A -d at the end of the example name means that domain propagation is used
for all occurring alldifferent and linear equation constraints. Likewise, -b
means that bounds(Z) propagation is used for all alldifferent and bounds(R)
for all linear equation constraints. In contrast, for -v bounds(R) propagation is
used for all linear constraints, whereas naive propagation (eliminating assigned
values as in Example 7.1) is used for alldifferent.
If not otherwise mentioned, bounds consistency is used for arithmetic constraints (including linear constraints) and naive propagation for alldifferent.
• all-interval-500 computes a series of numbers where the distances between adjacent numbers are pairwise distinct (prob007 in [10]). The model
uses a single bounds(Z) consistent alldifferent propagator and many
binary absolute value (abs(x) = y) and ternary minus propagators.

39

Table 14: Example characteristics.
Example
all-interval-500
alpha
bibd-7-3-60
cars
crowded-chess-7
donald-b
donald-d
donald-v
golomb-10-b
golomb-10-d
graph-color
grocery
knights-10
minsort-200
o-latin-7-d
partition-32
photo
picture
queens-400
queens-400-a
sequence-500
square-5-d
square-7-b
square-7-v
warehouse

variables
1 498
26
11 760
60
163
10
10
10
46
46
201
7
2 028
399
147
128
61
625
400
400
500
25
49
49
81

propagators
1 002
21
9 693
93
275
2
2
2
46
46
566
7
2 981
398
133
134
54
50
239 400
3
502
15
19
19
76

40

search
first
all
first
all
first
first
first
first
best
best
first
first
first
first
first
first
best
first
first
first
all
first
first
first
best

failures
0
7 435
1 306
107
30 396
79
5
79
19 929
19 929
37
37
2
0
2 188
160 258
6 995
3 242
10
10
250
41 272
245 208
481 301
20

solutions
1
1
1
6
1
1
1
1
10
10
1
1
1
1
1
1
7
1
1
1
1
1
1
1
4

• alpha and donald are crypto-arithmetic puzzles involving linear equation
propagators and a single alldifferent propagator.
• bibd-7-3-60 is an instance of a balanced incomplete block design problem
with parameters (v, k, l) = (7, 3, 60) (prob028 in [10]). The model involves
Boolean-sum propagators and lex propagators for symmetry breaking.
• cars models the well known car sequencing problem from [35] using element,
exactly, and linear equation propagators (prob001 in [10]).
• crowded-chess-7 places several different chess pieces on a 7 × 7 chessboard [11]. It uses exactly, element, domain consistent alldifferent,
and bounds(R) consistent linear equation propagators.
• golomb-10 finds an optimal Golomb ruler of size 10 (prob006 in [10]) with
the usual model.
• graph-color performs clique-based graph coloring for a graph with 200
nodes. Coloring each clique uses a domain consistent alldifferent propagator.
• grocery is a small crypto-arithmetic puzzle using in particular bounds(R)
consistent multiplication propagators.
• knights-10 finds a sequence of knight moves on a 10×10 chess board such
that each field is visited exactly once and that the moves return the knight
to the starting field. The model uses a naive alldifferent propagator
and a large number of reified binary propagators.
• minsort-200 sorts 200 variables using 200 minimum propagators.
• o-latin-7 finds an orthogonal latin square of size 7 and mostly uses
domain consistent alldifferent propagators.
• partition-32 partitions two 32 number blocks such that their products
match. Uses several bounds(R) multiplication propagators, a single domain consistent alldifferent propagator, and few linear equation propagators.
• photo places 9 persons on a picture such that as many preferences as
possible are satisfied. Uses a large bounds(Z) consistent alldifferent
propagator, a large bounds(R) consistent linear propagator, and many
reified binary propagators.
• picture models a 25×25 picture-puzzle (prob012 in [10]) using 50 regular
propagators.
• queens-400 and queens-400-a places 400 queens on a 400 × 400 chess
board such that the queens do not attack each other. queens-400 uses
quadratically many binary disequality propagators, while queens-400-a
uses three naive alldifferent-propagators.
41

• sequence-500 computes a magic sequence with 500 elements using 500
exactly propagators (prob019 in [10]).
• square-5 (square-7) computes a magic square of size 5 × 5 (7 × 7) using linear equation propagators and a single alldifferent propagator
(prob019 in [10]).
• warehouse solves a warehouse location problem following [32].

B

Evaluation Platform

All experiments use Gecode, a C++-based constraint programming library [12].
Gecode is one of the fastest constraint programming systems currently available,
benchmarks comparing Gecode to other systems are available from Gecode’s
webpage. The version used in this paper corresponds to Gecode 1.3.0 (albeit
slightly modified to ease the numerous experiments in this paper). Gecode has
been compiled with Microsoft Visual Studio Express Edition 2005.
All examples have been run on a Laptop with a 2 GHz Pentium M CPU
and 1024 MB main memory running Windows XP. Runtimes are the average of
25 runs with a coefficient of deviation less than 4% for all benchmarks.

Acknowledgments
Christian Schulte is partially funded by the Swedish Research Council (VR)
under grant 621-2004-4953. We thank Mikael Lagerkvist and Guido Tack for
many helpful suggestions that improved the paper.

References
[1] Krzysztof Apt. Principles of Constraint Programming. Cambridge University Press, Cambridge, United Kingdom, 2003.
[2] Philippe Baptiste, Claude Le Pape, and Wim Nuijten. Constraint-based
Scheduling. Kluwer Academic Publishers, Dordrecht, The Netherlands,
2001.
[3] Nicolas Beldiceanu, Warwick Harvey, Martin Henz, François Laburthe, Eric
Monfroy, Tobias Müller, Laurent Perron, and Christian Schulte. Proceedings of TRICS: Techniques foR Implementing Constraint programming Systems, a post-conference workshop of CP 2000. Technical Report TRA9/00,
School of Computing, National University of Singapore, September 2000.
[4] Frederic Benhamou. Heterogeneous Constraint Solving. In Proceedings of
the Fifth International Conference on Algebraic and Logic Programming,
volume 1139 of LNCS, pages 62–76, Aachen, Germany, 1996. SpringerVerlag.

42

[5] Mats Carlsson and Nicolas Beldiceanu. Revisiting the lexicographic ordering constraint. Technical Report T2002-17, Swedish Institute of Computer
Science, Stockholm, Sweden, 2002.
[6] Mats Carlsson, Greger Ottosson, and Björn Carlson. An open-ended finite
domain constraint solver. In Programming Languages: Implementations,
Logics, and Programs, 9th International Symposium, PLILP’97, volume
1292 of LNCS, pages 191–206, Southampton, United Kingdom, September
1997. Springer-Verlag.
[7] Andre Chamard, Annie Fischler, Dominique-Benoit Guinaudeau, and Andre Guillard. CHIC lessons on CLP methodology. Technical report, Dassault Aviation, 1995.
[8] Chiu Wo Choi, Warwick Harvey, Jimmy Ho-Man Lee, and Peter J.
Stuckey. Finite domain bounds consistency revisited. Technical report,
http://arxiv.org/abs//0412021, 2004.
[9] Philippe Codognet and Daniel Diaz. Compiling constraints in clp(FD).
Journal of Logic Programming, 27(3):185–226, June 1996.
[10] CSPLib. CSPLib: a problem library for constraints, 2006. Available from
http://www.csplib.org.
[11] Henry E. Dudeney. Amusements in Mathematics. Dover, New York, NY,
USA, 1958.
[12] Gecode Team. Gecode: Generic constraint development environment, 2006.
Available from http://www.gecode.org.
[13] Ian P. Gent, Chris Jefferson, and Ian Miguel. Watched literals for constraint
propagation in Minion. In Frédéric Benhamou, editor, Twelfth International Conference on Principles and Practice of Constraint Programming,
volume 4204 of LNCS, pages 182–197. Springer-Verlag, Nantes, France,
September 2006.
[14] Laurent Granvilliers and Eric Monfroy. Implementing constraint propagation by composition of reductions. In Logic Programming: Proceedings of
the 19th International Conference, volume 2916 of LNCS, pages 300–314,
Mumbai, India, 2003. Springer-Verlag.
[15] Warwick Harvey. Personal communication, April 2004.
[16] Warwick Harvey and Peter J. Stuckey. Improving linear constraint propagation by changing constraint representation. Constraints, 8(2):173–207,
2003.
[17] ILOG S.A. ILOG Solver 5.0: Reference Manual. Gentilly, France, August
2000.

43

[18] Intelligent Systems Laboratory. SICStus Prolog user’s manual, 3.11.1.
Technical report, Swedish Institute of Computer Science, Box 1263, 164
29 Kista, Sweden, 2004.
[19] François Laburthe. CHOCO: implementing a CP kernel. In Beldiceanu
et al. [3], pages 71–85.
[20] Olivier Lhomme, Arnaud Gotlieb, and Michel Rueher. Dynamic optimization of interval narrowing algorithms. Journal of Logic Programming, 37(1–
3):165–183, 1998.
[21] Alan K. Mackworth. Consistency in networks of relations. Artificial Intelligence, 8(1):99–118, 1977.
[22] Kim Marriott and Peter J. Stuckey. Programming with Constraints: an
Introduction. The MIT Press, Cambridge, MA, USA, 1998.
[23] Roger Mohr and Thomas C. Henderson. Arc and path consistency revisited.
Artificial Intelligence, 28:225–233, 1986.
[24] Roger Mohr and Gérald Masini. Good old discrete relaxation. In Yves
Kodratoff, editor, Proceedings of the 8th European Conference on Artificial
Intelligence (ECAI 88), pages 651–656, Munich, Germany, 1988. Pitmann
Publishing.
[25] Matthew W. Moskewicz, Conor F. Madigan, Ying Zhao, Lintao Zhang, and
Sharad Malik. Chaff: Engineering an efficient SAT solver. In Proceedings
of the 38th Design Automation Conference, DAC 2001, pages 530–535, Las
Vegas, NV, USA, 2001. ACM.
[26] Mozart Consortium. The Mozart programming system, 1999. Available
from www.mozart-oz.org.
[27] Gilles Pesant. A regular language membership constraint for finite sequences of variables. In Mark Wallace, editor, Tenth International Conference on Principles and Practice of Constraint Programming, volume 3258
of LNCS, pages 482–495. Springer-Verlag, Toronto, Canada, September
2004.
[28] Jean-Francois. Puget. A fast algorithm for the bound consistency of alldiff
constraints. In Proceedings of the 15th National Conference on Artificial
Intelligence (AAAI-98), pages 359–366, Madison, WI, USA, July 1998.
AAAI Press/The MIT Press.
[29] Jean-Charles Régin. A filtering algorithm for constraints of difference in
CSPs. In Proceedings of the Twelfth National Conference on Artificial Intelligence, volume 1, pages 362–367, Seattle, WA, USA, 1994. AAAI Press.
[30] Pierre Savéant. Constraint reduction at the type level. In Beldiceanu et al.
[3], pages 16–29.
44

[31] Christian Schulte and Peter J. Stuckey. When do bounds and domain
propagation lead to the same search space? Transactions on Programming
Languages and Systems, 27(3):388–425, May 2005.
[32] Pascal Van Hentenryck. The OPL Optimization Programming Language.
The MIT Press, Cambridge, MA, USA, 1999.
[33] Pascal Van Hentenryck, Vijay Saraswat, and Yves Deville. Constraint
processing in cc(FD). Draft, 1991.
[34] Pascal Van Hentenryck, Vijay Saraswat, and Yves Deville. Design, implementation and evaluation of the constraint language cc(FD). Journal of
Logic Programming, 37(1–3):139–164, 1998.
[35] Pascal Van Hentenryck, Helmut Simonis, and Mehmet Dincbas. Constraint
satisfaction using constraint logic programming. Artificial Intelligence,
58:113–159, 1992.
[36] Mark Wallace, Stefano Novello, and Joachim Schimpf. Eclipse: A platform
for constraint logic programming. Technical report, IC-Parc, Imperial College, London, GB, August 1997.
[37] Neng-Fa Zhou. Programming finite-domain constraint propagators in action rules. Theory and Practice of Logic Programming, 6(5):483–508,
September 2006.

45

