Explaining Constraint Programming
Krzysztof R. Apt1,2,3

arXiv:cs/0602027v1 [] 7 Feb 2006

1

School of Computing, National University of Singapore
2
CWI, Amsterdam
3
University of Amsterdam, the Netherlands

Abstract. We discuss here constraint programming (CP) by using a proof-theoretic perspective. To this end we identify three levels of abstraction. Each level
sheds light on the essence of CP.
In particular, the highest level allows us to bring CP closer to the computation
as deduction paradigm. At the middle level we can explain various constraint
propagation algorithms. Finally, at the lowest level we can address the issue of
automatic generation and optimization of the constraint propagation algorithms.

1 Introduction
Constraint programming is an alternative approach to programming which consists
of modelling the problem as a set of requirements (constraints) that are subsequently
solved by means of general and domain specific methods.
Historically, constraint programming is an outcome of a long process that has started
in the seventies, when the seminal works of Waltz and others on computer vision (see,
e.g.,[30]) led to identification of constraint satisfaction problems as an area of Artificial
Intelligence. In this area several fundamental techniques, including constraint propagation and enhanced forms of search have been developed.
In the eighties, starting with the seminal works of Colmerauer (see, e.g., [16]) and
Jaffar and Lassez (see [21]) the area constraint logic programming was founded. In the
nineties a number of alternative approaches to constraint programming were realized,
in particular in ILOG solver, see e.g., [20], that is based on modeling the constraint
satisfaction problems in C++ using classes. Another, recent, example is the Koalog
Constraint Solver, see [23], realized as a Java library.
This way constraint programming eventually emerged as a distinctive approach to
programming. In this paper we try to clarify this programming style and to assess it using a proof-theoretic perspective considered at various levels of abstraction. We believe
that this presentation of constraint programming allows us to more easily compare it
with other programming styles and to isolate its salient features.

2 Preliminaries
Let us start by introducing the already mentioned concept of a constraint satisfaction
problem. Consider a sequence X = x1 , . . ., xm of variables with respective domains
D1 , . . ., Dn . By a constraint on X we mean a subset of D1 × . . . × Dm . A constraint

satisfaction problem (CSP) consists of a finite sequence of variables x1 , . . ., xn with
respective domains D1 , . . ., Dn and a finite set C of constraints, each on a subsequence
of X. We write such a CSP as
hC ; x1 ∈ D1 , . . ., xn ∈ Dn i.
A solution to a CSP is an assignment of values to its variables from their domains
that satisfies all constraints. We say that a CSP is consistent if it has a solution, solved
if each assignment is a solution, and failed if either a variable domain is empty or a
constraint is empty. Intuitively, a failed CSP is one that obviously does not have any
solution. In contrast, it is not obvious at all to verify whether a CSP is solved. So we
introduce an imprecise concept of a ‘manifestly solved’ CSP which means that it is
computationally straightforward to verify that the CSP is solved. So this notion depends
on what we assume as ‘computationally straightforward’.
In practice the constraints are written in a first-order language. They are then atomic
formulas or simple combinations of atomic formulas. One identifies then a constraint
with its syntactic description. In what follows we study CSPs with finite domains.

3 High Level
At the highest level of abstraction constraint programming can be seen as a task of
formulating specifications as a CSP and of solving it. The most common approach to
solving a CSP is based on a top-down search combined with constraint propagation.
The top-down search is determined by a splitting strategy that controls the splitting
of a given CSP into two or more CSPs, the ‘union’ of which (defined in the natural
sense) is equivalent to (i.e, has the same solutions as) the initial CSP. In the most common form of splitting a variable is selected and its domain is partitioned into two or
more parts. The splitting strategy then determines which variable is to be selected and
how its domain is to be split.
In turn, constraint propagation transforms a given CSP into one that is equivalent
but simpler, i.e, easier to solve. Each form of constraint propagation determines a notion
of local consistency that in a loose sense approximates the notion of consistency and
is computationally efficient to achieve. This process leads to a search tree in which
constraint propagation is alternated with splitting, see Figure 1.
So the nodes in the tree are CSPs with the root (level 0) being the original CSP.
At the even levels the constraint propagation is applied to the current CSP. This yields
exactly one direct descendant. At the odd levels splitting is applied to the current CSP.
This yields more than one descendant. The leaves of the tree are CSPs that are either
failed or manifestly solved. So from the leaves of the trees it is straightforward to collect
all the solutions to the original CSP.
The process of tree generation can be expressed by means of proof rules that are
used to express transformations of CSPs. In general we have two types of rules. The
deterministic rules transform a given CSP into another one. We write such a rule as:
φ
ψ

constraint propagation

splitting

constraint propagation

splitting

constraint propagation

Fig. 1. A search tree for a CSP

where φ and ψ are CSPs.
In turn, the splitting rules transform a given CSP into a sequence of CSPs. We write
such a rule as:
φ
ψ1 | . . . | ψn
where φ and ψ1 , . . ., ψn are CSPs.
It is now easy to define the notion of an application of a proof rule to a CSP. In
the case of a deterministic rule we just replace (after an appropriate renaming) the part
that matches the premise of the rule by the conclusion. In the case of a splitting rule we
replace (again after an appropriate renaming) the part that matches the premise of the
rule by one of the CSPs ψi from the rule conclusion.
We now say that a deterministic rule
φ
ψ
is equivalence preserving if φ and ψ are equivalent and that a splitting rule
φ
ψ1 | . . . | ψn
is equivalence preserving if the union of ψi ’s is equivalent to φ.
In what follows all considered rules will be equivalence preserving. In general, the
deterministic rules are more ‘fine grained’ than the constraint propagation step that is
modeled as a single ‘step’ in the search tree. In fact, our intention is to model constraint
propagation as a repeated application of deterministic rules. In the next section we shall
discuss how to schedule these rule applications efficiently.

The search for solutions can now be described by means of derivations, just like
in logic programming. In logic programming we have in general two types of finite
derivations: successful and failed. In the case of proof rules as defined above a new type
of derivations naturally arises.
Definition 1. Assume a finite set of proof rules.
– By a derivation we mean a sequence of CSPs such that each of them is obtained
from the previous one by an application of a proof rule.
– A finite derivation is called
• successful if its last element is a first manifestly solved CSP in this derivation,
• failed if its last element is a first failed CSP in this derivation,
• stabilizing if its last element is a first CSP in this derivation that is closed under
the applications of the considered proof rules.
✷
The search for a solution to a CSP can now be described as a search for a successful
derivation, much like in the case of logic programming. A new element is the presence
of stabilizing derivations.
One of the main problems constraint programming needs to deal with is how to limit
the size of a search tree. At the high level of abstraction this matter can be addressed by
focusing on the derivations in which the applications of splitting rules are postponed as
long as possible. This bring us to a consideration of stabilizing derivations that involve
only deterministic rules. In practice such derivations are used to model the process of
constraint propagation. They do not lead to a manifestly solved CSP but only to a CSP
that is closed under the considered deterministic rules. So solving the resulting CSP
requires first an application of a splitting rule. (The resulting CSP can be solved but to
determine it may be computationally expensive.)
This discussion shows that at a high level of abstraction constraint programming
can be viewed as a realization of the computation as deduction paradigm according
to which the computation process is identified with a constructive proof of a formula
from a set of axioms. In the case of constraint programming such a constructive proof
is a successful derivation. Each such derivation yields at least one solution to the initial
CSP.
Because so far no specific rules are considered not much more can be said at this
level. However, this high level of abstraction allows us to set the stage for more specific
considerations that belong to the middle level.

4 Middle Level
The middle level is concerned with the form of derivations that involve only deterministic rules. It allows us to explain the constraint propagation algorithms which are
used to enforce constraint propagation. In our framework these algorithms are simply
efficient schedulers of appropriate deterministic rules. To clarify this point we now introduce examples of specific classes of deterministic rules. In each case we discuss a
scheduler that can be used to schedule the considered rules.

Example 1: Domain Reduction Rules
These are rules of the following form:
hC ; x1 ∈ D1 , . . ., xn ∈ Dn i
hC ′ ; x1 ∈ D1′ , . . ., xn ∈ Dn′ i
where Di′ ⊆ Di for all i ∈ [1..n] and C ′ is the result of restricting each constraint in C
to D1′ , . . ., Dn′ .
We say that such a rule is monotonic if, when viewed as a function f from the
original domains D1 , . . ., Dn to the reduced domains D1′ , . . ., Dn′ , i.e.,
f (D1 , . . ., Dn ) := (D1′ , . . ., Dn′ ),
it is monotonic:
Di ⊆ Ei for all i ∈ [1..n] implies f (D1 , . . ., Dn ) ⊆ f (E1 , . . ., En ).
That is, smaller variable domains yield smaller reduced domains.
Now, the following useful result shows that a large number of domain reduction
rules are monotonic.
Theorem 1. ([10]) Suppose each Di′ is obtained from Di using a combination of
–
–
–
–
–

union and intersection operations,
transposition and composition operations applied to binary relations,
join operation ✶,
projection functions, and
removal of an element.
Then the domain reduction rule is monotonic.

This repertoire of operations is sufficient to describe typical domain reduction rules
considered in various constraint solvers used in constraint programming systems, including solvers for Boolean constraints, linear constraints over integers, and arithmetic
constraints over reals, see, e.g., [10].
Monotonic domain reduction rules are useful for two reasons. First, we have the
following observation.
Note 1. Assume a finite set of monotonic domain reduction rules and an initial CSP P.
Every stabilizing derivation starting in P yields the same outcome.
Second, monotonic domain reduction rules can be scheduled more efficiently than
by means of a naive round-robin strategy. This is achieved by using a generic iteration
algorithm which in its most general form computes the least common fixpoint of a set
of functions F in an appropriate partial ordering. This has been observed in varying
forms of generality in the works of [12], [28], [17] and [7]. This algorithm has the
following form. We assume here a finite set of functions F , each operating on a given
partial ordering with the least element ⊥.

G ENERIC I TERATION algorithm
d := ⊥;
G := F ;
WHILE G 6= ∅ DO
choose g ∈ G;
IF d 6= g(d) THEN
G := G ∪ update(G, g, d);
d := g(d)
ELSE
G := G − {g}
END
END
where for all G, g, d
A {f ∈ F − G | f (d) = d ∧ f (g(d)) 6= g(d)} ⊆ update(G, g, d).
The intuition behind the assumption A is that update(G, g, d) contains at least all
the functions from F − G for which d is a fixpoint but g(d) is not. So at each loop
iteration if d 6= g(d), such functions are added to the set G. Otherwise the function g is
removed from G.
An obvious way to satisfy assumption A is by using the following update function:
update(G, g, d) := {f ∈ F − G | f (d) = d ∧ f (g(d)) 6= g(d)}.
The problem with this choice of update is that it is expensive to compute because for
each function f in F − G we would have to compute the values f (g(d)) and f (d). So in
practice, we are interested in some approximations from above of this update function
that are easy to compute. We shall return to this matter in a moment.
First let us clarify the status of the above algorithm. Recall that a function f on a
partial ordering (D, ⊑ ) is called monotonic if x ⊑ y implies f (x) ⊑ f (y) for all x, y
and inflationary if x ⊑ f (x) for all x.
Theorem 2. ([7]) Suppose that (D, ⊑ ) is a finite partial ordering with the least element ⊥. Let F be a finite set of monotonic and inflationary functions on D. Then every
execution of the G ENERIC I TERATION algorithm terminates and computes in d the least
common fixpoint of the functions from F .
In the applications we study the iterations carried out on a partial ordering that is a
Cartesian product of the component partial orderings. More precisely, given n partial
orderings (Di , ⊑ i ), each with the least element ⊥i , we assume that each considered
function g is defined on a ‘partial’ Cartesian product Di1 × . . . × Dil . Here i1 , . . ., il
is a subsequence of 1, . . ., n that we call the scheme of g. Given d ∈ D1 × · · · × Dn ,
where d := d1 , . . ., dn , and a scheme s := i1 , . . ., il we denote by d[s] the sequence
di1 , . . ., dil .
The corresponding instance of the above G ENERIC I TERATION algorithm then takes
the following form.

G ENERIC I TERATION FOR C OMPOUND D OMAINS algorithm
d := (⊥1 , . . ., ⊥n );
d′ := d;
G := F ;
WHILE G 6= ∅ DO
choose g ∈ G;
d′ [s] := g(d[s]), where s is the scheme of g;
IF d′ [s] 6= d[s] THEN
G := G ∪ {f ∈ F | scheme of f includes i such that d[i] 6= d′ [i]};
d[s] := d′ [s]
ELSE
G := G − {g}
END
END
So this algorithm uses an update function that is straightforward to compute. It simply checks which components of d are modified and selects the functions that depend
on these components. It is a standard scheduling algorithm used in most constraint programming systems.
Example 2: Arc Consistency
Arc consistency, introduced in [24], is the most popular notion of local consistency
considered in constraint programming. Let us recall the definition.
Definition 2.
– Consider a binary constraint C on the variables x, y with the domains Dx and Dy ,
that is C ⊆ Dx × Dy . We call C arc consistent if
• ∀a ∈ Dx ∃b ∈ Dy (a, b) ∈ C,
• ∀b ∈ Dy ∃a ∈ Dx (a, b) ∈ C.
– We call a CSP arc consistent if all its binary constraints are arc consistent.
So a binary constraint is arc consistent if every value in each domain has a support
in the other domain, where we call b a support for a if the pair (a, b) (or, depending on
the ordering of the variables, (b, a)) belongs to the constraint.
In the literature several arc consistency algorithms have been proposed. Their purpose is to transform a given CSP into one that is arc consistent without losing any solution. We shall now illustrate how the most popular arc consistency algorithm, AC-3,
due to [24], can be explained as a specific scheduling of the appropriate domain reduction rules. First, let us define the notion of arc consistency in terms of such rules.
Assume a binary constraint C on the variables x, y. We introduce the following two
rules.

ARC CONSISTENCY 1

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

hC ; x ∈ Dx , y ∈ Dy i
hC ; x ∈ Dx , y ∈ Dy′ i
where Dy′ := {b ∈ Dy | ∃ a ∈ Dx (a, b) ∈ C}.
So in each rule a selected variable domain is reduced by retaining only the supported
values. The following observation characterizes the notion of arc consistency in terms
of the above two rules.
Note 2 (Arc Consistency). A CSP is arc consistent iff it is closed under the applications
of the ARC CONSISTENCY rules 1 and 2.
So to transform a given CSP into an equivalent one that is arc consistent it suffices to repeatedly apply the above two rules for all present binary constraints. Since
these rules are monotonic, we can schedule them using the G ENERIC I TERATION FOR
C OMPOUND D OMAINS algorithm. However, in the case of the above rules an improved
generic iteration algorithm can be employed that takes into account commutativity and
idempotence of the considered functions, see [8].
Recall that given two functions f and g on a partial ordering we say that f is idempotent if f (f (x)) = f (x) for all x and say that f and g commute if f (g(x)) = g(f (x))
for all x. The relevant observation concerning these two properties is the following.
Note 3. Suppose that all functions in F are idempotent and that for each function g we
have a set of functions Comm(g) from F such that each element of Comm(g) commutes with g. If update(G, g, d) satisfies the assumption A, then so does the function
update(G, g, d) − Comm(g).
In practice it means that in each iteration of the generic iteration algorithm less
functions need to be added to the set G. This yields a more efficient algorithm.
In the case of arc consistency for each binary constraint C the functions corresponding to the ARC CONSISTENCY rules 1 and 2 referring to C commute. Also, given two
binary constraints that share the first (resp. second) variable, the corresponding ARC
CONSISTENCY rules 1 (resp. 2) for these two constraints commute, as well. Further,
all such functions are idempotent. So, thanks to the above Note, we can use an appropriately ‘tighter’ update function. The resulting algorithm is equivalent to the AC-3
algorithm.

Example 3: Constructive Disjunction
One of the main reasons for combinatorial explosion in search for solutions to a CSP are
disjunctive constraints. A typical example is the following constraint used in scheduling problems:
Start[task1 ] + Duration[task1 ] ≤ Start[task2 ] ∨
Start[task2 ] + Duration[task2 ] ≤ Start[task1 ]
stating that either task1 is scheduled before task2 or vice versa. To deal with a
disjunctive constraint we can apply the following splitting rule (we omit here the information about the variable domains):
C1 ∨ C2
C1 | C2
which amounts to a case analysis.
However, as already explained in Section 3 it is in general preferable to postpone an
application of a splitting rule and try to reduce the domains first. Constructive disjunction, see [29], is a technique that occasionally allows us to do this. It can be expressed
in our rule-based framework as a domain reduction rule that uses some auxiliary derivations as side conditions:
CONSTRUCTIVE DISJUNCTION

hC1 ∨ C2 ; x1 ∈ D1 , . . ., xn ∈ Dn i
hC1′ ∨ C2′ ; x1 ∈ D1′ ∪ D1′′ , . . ., xn ∈ Dn′ ∪ Dn′′ i

where

der1 , der2

with
der1 := hC1 ; x1 ∈ D1 , . . ., xn ∈ Dn i ⊢ hC1′ ; x1 ∈ D1′ , . . ., xn ∈ Dn′ i,
der2 := hC2 ; x1 ∈ D1 , . . ., xn ∈ Dn i ⊢ hC2′ ; x1 ∈ D1′′ , . . ., xn ∈ Dn′′ i,
and where C1′ is the result of restricting the constraint in C1 to D1′ , . . ., Dn′ and similarly
for C2′ .
In words: assuming we reduced the domains of each disjunct separately, we can
reduce the domains of the disjunctive constraint to the respective unions of the reduced
domains. As an example consider the constraint
h|x − y| = 1 ; x ∈ [4..10], y ∈ [2..7]i.
We can view |x − y| = 1 as the disjunctive constraint (x − y = 1) ∨ (y − x = 1). In
the presence of the ARC CONSISTENCY rules 1 and 2 rules we have then
hx − y = 1 ; x ∈ [4..10], y ∈ [2..7]i ⊢ hx − y = 1 ; x ∈ [4..8], y ∈ [3..7]i

and
hy − x = 1 ; x ∈ [4..10], y ∈ [2..7]i ⊢ hy − x = 1 ; x ∈ [4..6], y ∈ [5..7]i.
So using the CONSTRUCTIVE DISJUNCTION rule we obtain
h|x − y| = 1 ; x ∈ [4..8], y ∈ [3..7]i.
If each disjunct of a disjunctive constraint is a conjunction of constraints, the auxiliary derivations in the side conditions can be longer than just one step. Once the rules
used in these derivations are of an appropriate format, their applications can be scheduled using one of the discussed generic iteration algorithms. Then the single application
of the CONSTRUCTIVE DISJUNCTION rule consists in fact of two applications of the
appropriate iteration algorithm.
It is straightforward to check that if the auxiliary derivations involve only monotonic domain reduction rules, then the CONSTRUCTIVE DISJUNCTION rule is itself
monotonic. So the G ENERIC I TERATION FOR C OMPOUND D OMAINS algorithm can
be applied both within the side conditions of this rule and for scheduling this rule together with other monotonic domain reduction rules that are used to deal with other,
non-disjunctive, constraints.
In this framework it is straightforward to formulate some strengthenings of the constructive disjunction that lead to other modification of the constraints C1 and C2 than
C1′ and C2′ .
Example 4: Propagation Rules
These are rules that allow us to add new constraints. Assuming a given set A of ‘allowed’ constraints we write such rules as

B
C
where B, C ⊆ A.
This rule states that in presence of all constraints in B the constraints in C can be
added, and is a shorthand for a deterministic rule of the following form:

hB ; x1 ∈ D1 , . . ., xn ∈ Dn i
hB, C ; x1 ∈ D1 , . . ., xn ∈ Dn i
An example of such a rule is the transitivity rule:

x < y, y < z
x<z

that refers to a linear ordering < on the underlying domain (for example natural numbers).
In what follows we focus on another example of propagation rules, membership
rules. They have the following form:
y1 ∈ S1 , . . ., yk ∈ Sk
z1 6= a1 , . . ., zm 6= am
where yi ∈ Si and zj 6= aj are unary constraints with the obvious meaning.
Below we write such a rule as:
y1 ∈ S1 , . . ., yk ∈ Sk → z1 6= a1 , . . ., zm 6= am .
The intuitive meaning of this rule is: if for all i ∈ [1..k] the domain of each yi is a subset
of Si , then for all j ∈ [1..m] remove the element aj from the domain of zj .
The membership rules allow us to reason about constraints given explicitly in a form
of a table. As an example consider the three valued logic of Kleene. Let us focus on the
conjunction constraint and3(x, y, z) defined by the following table:
t fu
t t fu
f fff
uufu
That is, and3 consists of 9 triples. Then the membership rule y ∈ {u, f } → z 6= t, or
more precisely the rule
hand3(x, y, z), y ∈ {u, f } ; x ∈ Dx , y ∈ Dy , z ∈ Dz i
hand3(x, y, z), y ∈ {u, f }, z 6= t ; x ∈ Dx , y ∈ Dy , z ∈ Dz i
is equivalence preserving. This rule states that if y is either u or f , then t can be removed
from the domain of z.
We call a membership rule is minimal if it is equivalence preserving and its conclusions cannot be established by either removing from its premise a variable or by
expanding a variable range. For example, the above rule y ∈ {u, f} → z 6= t is minimal, while neither x ∈ {u}, y ∈ {u, f } → z 6= t nor y ∈ {u} → z 6= t is. In the case
of the and3 constraint there are 18 minimal membership rules.
To clarify the nature of the membership rules let us mention that, as shown in [9],
in the case of two-valued logic the corresponding set of minimal membership rules
entails a form of constraint propagation that is equivalent to the unit propagation, a
well-known form of resolution for propositional logic. So the membership rules can be
seen as a generalization of the unit propagation to the explicitly given constraints, in
particular to the case of many valued logics.
Membership rules can be alternatively viewed as a special class of monotonic domain reductions rules in which the domain of each zi variable is modified by removing

ai from it. So we can schedule these rules using the G ENERIC I TERATION FOR C OM POUND D OMAINS algorithm.
However, the propagation rules, so in particular the membership rules, satisfy an
important property that allows us to schedule them using a more efficient, fine-tuned,
scheduler. We call this property stability. It states that in each derivation the rule needs
to be applied at most once: if it is applied, then it does not need to be applied again.
So during the computation the applied rules that are stable can be permanently removed
from the initial rule set. The resulting scheduler for the membership rules and its further
optimizations are discussed in [14].

5 Low Level
The low level allows us to focus on matters that go beyond the issue of rule scheduling.
At this level we can address matters concerned with further optimization of the constraint propagation algorithms. Various improvements of the AC-3 algorithm that are
concerned with specific choices of the data structures used belong here but cannot be
explained by focusing the discussion on the corresponding ARC CONSISTENCY 1 and
2 rules.
On the other hand some other optimization issues can be explained in proof-theoretic
terms. In what follows we focus on the membership rules for which we worked out the
details. These rules allow us to implement constraint propagation for explicitly given
constraints. We explained above that they can be scheduled using a fine-tuned scheduler. However, even when an explicitly given constraint is small, the number of minimal
membership rules can be large and it is not easy to find them all.
So a need arises to generate such rules automatically. This is what we did in [11].
We also proved there that the resulting form of constraint propagation is equivalent to
hyper-arc consistency, a natural generalization of arc consistency to n-ary constraints
introduced in [25].
A further improvement can be achieved by removing some rules before scheduling
them. This idea was pursued in [14]. Given a set of monotonic domain reduction rules
R we say that a rule r is redundant if for each initial CSP P the unique outcome of
a stabilizing derivation (guaranteed by Note 1) is the same with r removed from R. In
general, the iterated removal of redundant rules does not yield a unique outcome but in
the case of the membership rules some useful heuristics can be used to appropriately
schedule the candidate rules for removal.
We can summarize the improvements concerned with the membership rules as follows:
– For explicitly given constraints all minimal membership rules can be automatically
generated.
– Subsequently redundant rules can be removed.
– A fine-tuned scheduler can be used to schedule the remaining rules.
– This scheduler allows us to remove permanently some rules which is useful during
the top-down search.

To illustrate these matters consider the 11-valued and11 constraint used in the
automatic test pattern generation (ATPG) systems. There are in total 4656 minimal
membership rules. After removing the redundant rules only 393 remain. This leads to
substantial gains in computing. To give an idea of the scale of the improvement here
are the computation times in seconds for three schedulers used to find all solutions to a
CSP consisting of the and11 constraint and solved using a random variable selection,
domain ordering and domain splitting:

Fine-tuned Generic CHR
all rules
1874
3321 7615
non-redundant rules 157
316
543

CHR stands for the standard CHR scheduler normally used to schedule such rules. (CHR
is a high-level language extension of logic programming used to write user-defined
constraints, for an overview see [18].) So using this approach a 50 fold improvement in
computation time was achieved. In general, we noted that the larger the constraint the
larger the gain in computing achieved by the above approach.

6 Conclusions
In this paper we assessed the crucial features of constraint programming (CP) by means
of a proof-theoretic perspective. To this end we identified three levels of abstraction.
At each level proof rules and derivations played a crucial role. At the highest level
they allowed us to clarify the relation between CP and the computation as deduction
paradigm. At the middle level we discussed efficient schedulers for specific classes of
rules. Finally, at the lowest level we explained how specific rules can be automatically
generated, optimized and scheduled in a customized way.
This presentation of CP suggests that it has close links with the rule-based programming. And indeed, several realizations of constraint programming through some form of
rule-based programming exist. For example, constraint logic programs are sets of rules,
so constraint logic programming can be naturally seen as an instance of rule-based
programming. Further, the already mentioned CHR language is a rule-based language,
though it does not have the full capabilities of constraint programming. In practise, CHR
is available as a library of a constraint programming system, for example ECLi PSe (see
[1]) or SICStus Prolog (see [3]). In turn, ELAN, see [2], is a rule-based programming
language that can be naturally used to explain various aspects of constraint programming, see for example [22] and [15].
In our presentation we abstracted from specific constraint programming languages
and their realizations and analyzed instead the principles of the corresponding programming style. This allowed us to isolate the essential features of constraint programming
by focusing on proof rules, derivations and schedulers. This account of constraint programming draws on our work on the subject carried out in the past seven years. In
particular, the high level view was introduced in [6]. In turn, the middle level summa-

rizes our work reported in [7,8]. Both levels are discussed in more detail in [10]. Finally,
the account of propagation rules and of low level draws on [11,14].
This work was pursued by others. Here are some representative references. Concerning the middle level, [26] showed that the framework of Section 4 allows us to
parallelize constraint propagation algorithms in a simple and uniform way, while [13]
showed how to use it to derive constraint propagation algorithms for soft constraints. In
turn, [19] explained other arc consistency algorithms by slightly extending this framework.
Concerning the lowest level, [27] considered rules in which parameters (i.e., unspecified constants) are allowed. This led to a decrease in the number of generated rules. In
turn, [4] presented an algorithm that generates more general and more expressive rules,
for example with variable equalities in the conclusion. Finally, [5] considered the problem of generating the rules for constraints defined intensionally over infinite domains.

Acknowledgments
The work discussed here draws partly on a joint research carried out with Sebastian
Brand and with Eric Monfroy. In particular, they realized the implementations discussed
in the section on the low level. We also acknowledge useful comments of the referees.

References
1. The
ECLi PSe
Constraint
Logic
Programming
System.
http://www-icparc.doc.ic.ac.uk/eclipse/.
2. ELAN, Version 3.3. http://www.iist.unu.edu/˜alumni/software/other/inria/www/elan/elan-prese
3. SICStus Prolog. http://www.sics.se/isl/sicstuswww/site/index.html.
4. S. Abdennadher and Ch. Rigotti. Automatic generation of rule-based constraint solvers over
finite domains. ACM Transactions on Computational Logic, 5(2):177–205, 2004.
5. S. Abdennadher and Ch. Rigotti. Automatic generation of CHR constraint solvers. Theory
and Practice of Logic Programming, 2005. To appear.
6. K. R. Apt. A proof theoretic view of constraint programming. Fundamenta Informaticae,
33(3):263–293, 1998. Available via http://arXiv.org/archive/cs/.
7. K. R. Apt. The essence of constraint propagation. Theoretical Computer Science, 221(1–
2):179–210, 1999. Available via http://arXiv.org/archive/cs/.
8. K. R. Apt. The role of commutativity in constraint propagation algorithms. ACM Transactions on Programming Languages and Systems, 22(6):1002–1036, 2000. Available via
http://arXiv.org/archive/cs/.
9. K. R. Apt. Some remarks on Boolean constraint propagation. In K. R. Apt, A. C.
Kakas, E. Monfroy, and F. Rossi, editors, New Trends in Constraints, volume 1865 of Lecture Notes in Artificial Intelligence, pages 91 – 107. Springer-Verlag, 2000. Available via
http://arXiv.org/archive/cs/.
10. K. R. Apt. Principles of Constraint Programming. Cambridge University Press, 2003.
11. K. R. Apt and E. Monfroy. Constraint programming viewed as rule-based programming. Theory and Practice of Logic Programming, 1(6):713–750, 2001. Available via
http://arXiv.org/archive/cs/.

12. F. Benhamou. Heterogeneous constraint solving. In M. Hanus and M. Rodriguez-Artalejo,
editors, Proceeding of the Fifth International Conference on Algebraic and Logic Programming (ALP 96), Lecture Notes in Computer Science 1139, pages 62–76, Berlin, 1996.
Springer-Verlag.
13. S. Bistarelli, R. Gennari, and F. Rossi. Constraint propagation for soft constraint satisfaction
problems: Generalization and termination conditions. In Rina Dechter, editor, Proceedings
of Constraint Programming 2000 (CP2000), Lecture Notes in Computer Science 1894, pages
83–97, Berlin, 2000. Springer-Verlag.
14. S. Brand and K. R. Apt. Schedulers and redundancy for a class of constraint propagation
rules. Theory and Practice of Logic Programming, 2005. To appear.
15. C. Castro. Building constraint satisfaction problem solvers using rewrite rules and strategies.
Fundamenta Informaticae, 33(3):263–293, 1998.
16. Alain Colmerauer. Opening the PROLOG-III universe. BYTE Magazine, 12(9), August
1987.
17. F. Fages, J. Fowler, and T. Sola. Experiments in reactive constraint logic programming.
Journal of Logic Programming, 37(1–3):185–212, 1998.
18. T. Frühwirth. Theory and practice of Constraint Handling Rules. Journal of Logic Programming, 37(1–3):95–138, October 1998. Special Issue on Constraint Logic Programming (P. J.
Stuckey and K. Marriot, Eds.).
19. R. Gennari. Arc consistency via subsumed functions. In John Lloyd, editor, Proceedings
of Computational Logic 2000 (CL2000), Lecture Notes in Artificial Intelligence 1861, pages
358–372, Berlin, 2000. Springer-Verlag.
20. ILOG.
Ilog
white
papers,
2003.
Available
via
http://www.ilog.com/products/optimization/papers.cfm.
21. J. Jaffar and J.-L. Lassez. Constraint logic programming. In POPL’87: Proceedings 14th
ACM Symposium on Principles of Programming Languages, pages 111–119. ACM, 1987.
22. C. Kirchner and C. Ringeissen. Rule-based constraint programming. Fundamenta Informaticae, 34(3):225–262, September 1998.
23. Koalog. http://www.koalog.com, 2005.
24. A. Mackworth. Consistency in networks of relations. Artificial Intelligence, 8(1):99–118,
1977.
25. R. Mohr and G. Masini. Good old discrete relaxation. In Y. Kodratoff, editor, Proceedings
of the 8th European Conference on Artificial Intelligence (ECAI), pages 651–656. Pitman
Publishers, 1988.
26. E. Monfroy and J.-H. Réty. Chaotic iteration for distributed constraint propagation. In
J. Carroll, H. Haddad, D. Oppenheim, B. Bryant, and G. Lamont, editors, Proceedings of the
14th ACM Symposium on Applied Computing, ACM SAC’99, Scientific Computing Track,
pages 19–24, San Antonio, Texas, USA, March 1999. ACM Press.
27. C. Ringeissen and E. Monfroy. Generating propagation rules for finite domains: a mixed
approach. In K. R. Apt, A. C. Kakas, E. Monfroy, and F. Rossi, editors, New Trends in Constraints, volume 1865 of Lecture Notes in Artificial Intelligence, pages 150–172. SpringerVerlag, 2000.
28. V. Telerman and D. Ushakov. Data types in subdefinite models. In J. A. Campbell J. Calmet
and J. Pfalzgraf, editors, Artificial Intelligence and Symbolic Mathematical Computations,
Lecture Notes in Computer Science 1138, pages 305–319, Berlin, 1996. Springer-Verlag.
29. P. Van Hentenryck, V. Saraswat, and Y. Deville. Design, implementation, and evaluation
of the constraint language cc(fd). Journal of Logic Programming, 37(1–3):139–164, 1998.
Special Issue on Constraint Logic Programming (P. J. Stuckey and K. Marriot, Eds.).
30. D. L. Waltz. Generating semantic descriptions from drawings of scenes with shadows. In
P. H. Winston, editor, The Psychology of Computer Vision, pages 19–91. McGraw Hill, 1975.

