Constraint Programming
Constraint programming is the study of computational models and
systems based on constraints. The idea is to model and solve a
problem by exploring the constraints that can fully characterize
the problem, hence any solution of the problem must satisfy all
of the stated constraints. Constraint programming is one of the
most exciting developments in programming languages in the last
decade. It is attracting widespread commercial interest and is now
becoming the method of choice for modeling any types of optimization
problems.
Constraint programming has been identified by ACM as one of Strategic Directions in Computing Research.
As stated by Eugene C. Freuder,
"Constraint programming represents one of the closest approaches computer
science has yet made to the Holy Grail of programming: the user states
the problem, the computer solves it."
Constraints have recently emerged as a research area that combines researchers from a number of fields, including
Artificial Intelligence, Programming Languages, Symbolic Computing and Computational Logic. Constraint networks
and constraint satisfaction problems have been studied in Artificial Intelligence starting from the seventies.
Systematic use of constraints in programming has started in the eighties. In constraint programming the programming
process consists of the generation of requirements (constraints) and solution of these requirements, by specialized
constraint solvers.
Constraint programming is intended to solve computationally hard problems.
These are combinatorial problems, graph-theoretic problems,
optimization problems, and problems involving scheduling and planning.
Constraint programming has been successfully applied in numerous domains. Recent applications include computer
graphics (to express geometric coherence in the case of scene analysis), natural language processing (construction of
efficient parsers), database systems (to ensure and/or restore consistency of the data), operations research problems
(like optimization problems), molecular biology (DNA sequencing), business applications (option trading), electrical
engineering (to locate faults), circuit design (to compute layouts), etc
Example. Cryptarithmetic puzzles
The problem is to assign distinct (decimal) digits to letters so that
adding two words yields the third. E.g.
For problems like this we can always guess a solution (an assignment of digits
to letters in this case). This is the so-called generate and test
approach. However, the number of possibilities may be too large to manage.
For instance, in the second example above 11 letters need to be assigned.
Each letter can be assigned
one of the 10 digits. Thus, there are potentially 10^11 = 100,000,000,000
possible assignments to check.
A constraint logic program can solve these problems in a fraction of a second.
Example. The queens problem
The queens problem: there is an 8 X 8 board on which to place
one queen on each row so that no queens are at the same column or
the same diagonal.
The search space for the problem is 8^8, a very large number.
If we scale up to 20 queens on a 20X20 board, the number
of possible solutions would be too huge.
A constraint logic program can solve the queens problem for 20 queens
within 20-30 seconds. Someone has solved this problem using constraint
programming for 100 queens.
For 20 queens, a naive Prolog program (e.g. the one found in
these notes) would need about 1 hour to get a solution.
Example Satisfiability checking
In AI, one of the useful yet difficult problems is to determine whether
a finite set of clauses is satisfiable. This is the well-known SAT problem.
A clause is a disjunction of literals
Many real world problems can be formulated as a SAT problem.
If we know how to solve
it efficiently, we will have an efficient solver for all of
these real world problems.
Search space: there are 2^N possible assignments, for N propositions.
This is because each proposition can be assigned to either true or false.
The value of 2^N grows exponentially with N. Say, we have used 100 atoms,
then the search space is 2^100, a huge number. Given an assignment, we
can easily determine whether it satisfies the give set of clauses.
But we just don't know which assignment to pick. We have to search for
a solution.
Example.
The blocks world
A simple yet computationally challenging planning problem.
We are given a table and a configuration of a number of blocks, each of
which is either on the table or on another block. Suppose the action
that we can take is to move a block X to Y which is another block or
the table, denoted by move(X,Y).
There are usually conditions under which
an action can take place. E.g. the action move(X,Y) can take place if
there is no block on X or Y.
A plan is a sequence of actions. The problem we want to solve is to
generate a plan so that a configuration can be reached from some initial
one.
One way to solve a constraint problem is to formalize it
as a constraint satisfaction problem.
A constraint satisfaction problem (CSP) consists of three parts:
Note that values need not be a set of consecutive integers (although
often they are), they need not even be numeric.
A solution to a CSP is an assignment of a value from its domain to every
variable, in such a way that every constraint is satisfied.
We may want to find:
Example
Suppose we have variables X,Y,Z, and their domains are
Example
Using the 4-queen problem as an example, we can use a variable to represent
each queen, thus we have 4 variables, say,
A constraint is local but a solution to all constraints is global.
For example, consider X < Y and Y < Z over the domain {1,2,3}
for all the variables. X=1 and Y=3 is a solution to the constraint
X < Y, but cannot give a solution when Y < Z is also considered.
Systematic Search Algorithms
A CSP can be solved using generate-and-test paradigm (GT) that systematically generates each possible
value assignment and then it tests to see if it satisfies all the constraints. A more efficient method uses the
backtracking paradigm (BT) that is the most common algorithm for performing systematic search.
Backtracking incrementally attempts to extend a partial solution toward a complete solution, by repeatedly
choosing a value for another variable.
Example
Consider X < Y and Y < Z over the domain {1,2,3}.
We assign a value to a variable, one at a time. Whenever a variable
is assigned, it's checked against all previous assignments to see
whether it's "so far so good" (the constraints involving these assigned
variables are not violated).
Consistency Techniques
Consider X < Y and Y < Z over the domain {1,2}. There is no solution
for this CSP, but we only discover that until Z is assigned.
The late detection of inconsistency is a major disadvantage of BT.
Thus, consistency techniques are applied during the backtrack search,
after each variable is assigned. The idea is to discover what
values are not possible so they can be safely removed for the
assignment so far (they are not removed permanently; they will be recovered
upon backtracking).
The most common techniques are node consistency and
arc consistency.
Node consistency only applies to constraint
with one unassigned variable, since it's trivial to check
what values for the variable are not possible, and therefore should
be removed.
For example, consider X > 2 over the domain {1,2,3,4} for X.
After we apply the node consistency, the domain for X is reduced to {3,4}.
The CSP where the constraint is X > 2 over the domain {3,4} for X is
called node consistent.
Arc consistency only applies to a constraint with two unassigned variables,
say X and Y. If for a value of X, there is no value of Y such that
the constraint is satisfied, then this value for X can be removed.
This is done repeatedly until no domain reduction is possible.
For example, consider X < Y and Y < Z over the domain
Dx = Dy = Dz = {1,2,3}.
Consider the constraint X < Y first.
Apparently, X=3 cannot give a solution for any Y. So Dx is reduced
to Dx1 = {1,2}. Similarly, we get Dy1={2,3}. Consider Y < Z.
Given Dy1={2,3}, the only value for Z that can satisfy the constraint
is Z=3, thus Dz={3}. Similarly, Dy1 is reduced to Dy2={2}. And finally,
Dx1 is reduced to Dx2={1}.
The CSP with constraints X < Y and Y < Z over the domain
Dx = {1}, Dy = {2}, and Dz = {3} is called arc consistent .
Additional Space Pruning Techniques
Refer to this document for further information.
In CLP, a number of constraint solvers may be embedded into Prolog,
typically including solvers over reals, rationals, boolean, and
perhaps the most useful one over finite domains.
This is typically based on the
general Constraint Logic Programming Scheme introduced
by Jaffar and Michaylov in 1987. The idea is this: unification
in Prolog is about solving constraints over equations in the sense of
pattern matching. Now, we may embed an arbitrary constraint solver
in the place of unification to solve, not only constraints over equations,
but constraints over other domains.
We can take a look at a simple example. Suppose we write a Prolog program:
Since we may have a conjunction of equations and inequations to solve,
let's leave it to a constraint store, a collection of some primitive constraints. Any non-user defined predicates
will be sent to the constraint store. Every time
a constraint store is modified, we check, and if we can determine
that it cannot be solved we can then stop right away. Then,
Prolog backtracks in the normal way.
We can sketch how this is done below where CS is
the constraint store at each step.
In any Prolog implementation, you have to use some specific syntax
in order to invoke an embedded constraint solver.
In Sicstus Prolog, you call a library package, and
write your program as:
The first line is to load the library for the solver over reals (CLPR).
The braces around an inequation (or an equation for that matter)
tells Sicstus Prolog that the inequation should be sent to the
constraint store and solved by CLPR. Now, if you type the goal
Example.
CLPFD is particularly suitable for solving CSPs.
It is claimed that about 90% of industrial applications
are finite domain constraints.
The constraint solver is useful for modeling
problems such as scheduling, planning, packing, timetabling, etc.
Recall that in order to solve a CSP, you need to determine
three things: the variables, their domains, and the constraints.
The overall structure of using Sicstus Prolog's finite domain solver is:
Writing constraints is very much like writing a Prolog program with
a specific syntax. We will get to see the syntax soon.
To tell Sicstus Prolog to assign a domain value to a variable, one by
one, until a satisfying assignment is found, you use labeling/2
(cf. this manual page). E.g.
Let's see a simple program of solving the problem:
can an integer N be expressed as N = C0 + C1*N1 + C2*N2*N2,
where C0,C1,N1,N2 are within the range [0,N]?
Now, assume you want the values of C0,C1,C2,N1,N2 to be in increasing order.
To also satisfy this constraint
, you can write
It is important to understand how labeling works. Consider this program:
The predicate labeling simply relies on Prolog's backtracking to get
domain variables instantiated. To understand it, let's write our own
labeling predicate as follows:
That is, xlabeling generates all combinations of X and Y by backtracking.
Now, let's see the use of xlabeling with constraints.
Now, we are in a position to see some interesting programs.
If your program gets somewhat more complex, you may want to read the following notes:
What is Constraint Programming
S E N D
+ M O R E
--------------
M O N E Y
D O N A L D
+ G E R A L D
--------------
R O B E R T
A Prolog solution can be found in Bratko p.150. The program given there
is quite hard to understand. In comparison, a constraint logic programming
solution, as we will see later, is very easy to understand.
l1 v ... v ln
A literal is either a proposition or a negated one.
A set of clauses is satisfied by an assignment iff each clause is satisfied.
A clause is satisfied iff there is at least one literal in it is true
in the assignment.
Constraint Satisfaction
1. A set of variables X={x1,...,xn}
2. For each variable xi, a finite set Di of possible values (its domain)
3. A set of constraints restricting the values that the variables can
simultaneously take.
-just one solution, with no preference as to which one,
-all solutions,
-an optimal, or at least a good solution, given some objective function
defined in terms of some or all of the variables.
D_X = D_Y = {1,2,3}, D_Z = {2,3,4}
and the constraints are
X < Y and Y < Z.
It's clear that this CSP is satisfiable. For example, the assignment
X=1, Y=2, Z=3
is a solution.
x1, x2, x3, x4
Assume x1 is placed on the first row, x2 on the second row, and so on.
The domain for each queen then consists of 4 columns. Thus, we have domains
for the variables as
D_x1 = {1,2,3,4},
D_x2 = {1,2,3,4},
D_x3 = {1,2,3,4},
D_x4 = {1,2,3,4},
The constraints that must be satisfied can be stated as relations.
E.g.
the constraint that says x1 and x2 cannot be on the same column can be
expressed by the set of tuples satisfying it:
r1(x1,x2) ={(1,2),(1,3),(1,4),
(2,1),(2,3),(2,4),
(3,1),(3,2),(3,4),
(4,1),(4,2),(4,3)}
Defining a relation by stating satisfied tuples is tedious.
In a suitable language, one may express this by
r1(x1,x2) if x1 is not equal to x2, and
x1 takes a value from D_x1 and x2 takes a value from D_x2
It's apparent that we need a language to express all three parts of a CSP.
We will see later that logic programming has been extended to
constraint logic programming (CLP) where constructs are provided to us
to express these.
Constraint Solving Methods
X assigned X=1
(so far so good) X < Y is not violated
/ \
Y assigned Y=1 Y=2
(no good) (so far so good) X < Y and Y < Z are not violated
/ | \
Z assigned Z=1 Z=2 Z=3
(no good)(no good) All var's are assigned
Constraint Logic Programming: a Brief Introduction
p(f(X)) :- X>1, q(X).
q(X) :- X<5.
If we call
?- p(Z).
we will get the complaint from Prolog that X is uninstantiated when trying
to solve X > 1. However, if we consider whether X > 1 is sovable over
real numbers, the answer is obvious: YES. In this case, we are not interested
in bindings of X (there are infinitely many),
but only the question whether it is satisfiable (solvable).
solve p(Z) CS = {}
|
V
X > 1, q(X) CS = {Z = f(X)}
|
V
q(X) CS = {Z = f(X), X > 1}
|
V
X < 5 CS = {Z = f(X), X > 1}
|
V CS = {Z = f(X), X > 1, X < 5}
[]
Now the answer to the original query lies in whether CS is sovable,
which we know is yes. So if a solver over equations and inequations
is embedded in Prolog, we will get a yes answer.
:- use_module(library(clpr)).
p(f(X)) :- {X>1}, q(X).
q(X) :- {X<5}.
?- p(Z)
you will get something like
Z = f(_A),
{_A<5.0},
{_A>1.0}
The last two lines indicate that these inequations are solvable.
:- use_module(library(clpr)).
p(f(X)) :- {X>1}, q(X).
q(X) :- {X<0}, g(X).
g(1).
solve p(Z) CS = {}
|
V
X > 1, q(X) CS = {Z = f(X)}
|
V
q(X) CS = {Z = f(X), X > 1}
|
V
X < 0, g(X) CS = {Z = f(X), X > 1}
|
V CS = {Z = f(X), X > 1, X < 0}
g(X)
In this case, we fail the proof, since CS is not solvable.
Solving CSPs using Sicstus Prolog's Finite Domain Sovler
In this course, we will be using
CLPFD, the package of Sicstus Prolog for solving constraint
problems over finite domains.
This implementation of Sicstus Prolog's finite domain solver employs node and
arc consistency methods. It also implements a method that can perform
domain reduction for constraints with more than two uninstantiated
variables. It is called bounds consistency. The idea is look
at the range of a domain, the lower bound and the upper bound, to
figure out whether the range can be narrowed. This can be done
for consecutive numerical domains. That's why it's called
bounds consistency. This is also the reason why in Sicstus Prolog's CLPFD,
finite domains must be consecutive integers.
-declare domains
-specify constraints
-tell Prolog to assign domain values to variables, one by one, until
a satisfying assignment is found.
In sicstus Prolog, you use the builtin predicate domain/3 (cf. this manual page) to declare variable and their
domains. E.g.
domain([X,Y,Z], 1,4)
says that the variables X, Y and Z have the domain {1,2,3,4}.
domain([X,Y], 1,4),
domain([Z], 3,5)
says that the variables X and Y have the domain {1,2,3,4},
and Z has domain {3,4,5}. As we said earlier, in Sicstus Prolog domain values must
be consecutive integers.
labeling([], [X,Y,Z])
assigns a domain value to X,Y,Z, in that order, one by one,
until a solution is found. In the first parameter of labeling/2, one
can specify some options. E.g. you can choose the order from Z to X
rather than from X to Z, or choose the variable that has the smallest
domain size. By leaving it [], you use the default options from left
to right, and domain values are picked in increasing order.
:- use_module(library(clpfd)).
solve(N,S) :-
S = [C0,C1,C2,N1,N2], %Let S be bound to a list of five variables
domain(S,0,N),
N #= C0 + C1*N1 + C2*N2*N2,
labeling([],S).
As an example of the syntax, you see = is headed by #.
Similarly for other comparisons: #\= (inequality),
#<, #=<, #>, #>=. (Cf.
this manual page.)
:- use_module(library(clpfd)).
% given N, S is a list [N1,N2] such that N1*N1 + N2*N2 = N
solve(N,S) :-
S = [C0,C1,N1,C2,N2],
domain(S,0,N),
my_constraint(N,C0,C1,N1,C2,N2),
labeling([],S).
my_constraint(N,C0,C1,N1,C2,N2) :-
N #= C0 + C1*N1 + C2*N2*N2,
C0 #=< C1, C1 #=< N1, N1 #=< C2, C2 #=< N2.
As one can see, you write constraints in the same way as you write a prolog program,
but using the CLPFD syntax. What if you don't use CLPFD syntax, say
instead
N #= C0 + C1*N1 + C2*N2*N2
you write
N is C0 + C1*N1 + C2*N2*N2
Then, this will be executed outside CLPFD, by Prolog. As a result,
since the variables at the right hand side are not instantiated, you will
get an error message.
%--------------------------------------------------------------------
% Without labeling, domain reductions are performed but
% you may not get a valuation
noLabeling(N,L) :-
L = [A,B,C],
domain([A,B,C],1,N),
A #> B, B #> C.
% test case
/*
| ?- noLabeling(4,L).
L = [_A,_B,_C],
_A in 3..4,
_B in 2..3,
_C in 1..2 ?
*/
Note that the domains for all three variables have been reduced.
Since no labeling is used, variables may not get a value.
xlabeling([]).
xlabeling([V|Vs]) :- indomain(V), xlabeling(Vs).
% where indomian is a CLPFD built-in predicate that assigns domain values
% to V in increasing order via backtracking.
goal(X,Y) :- domain([X,Y],1,3), xlabeling([X,Y]).
{trace}
| ?- goal(X,Y).
1 1 Call: goal(_181,_201) ?
2 2 Call: domain([_181,_201],1,3) ?
2 2 Exit: domain([_1054,_1085],1,3) ?
3 2 Call: xlabeling([_1054,_1085]) ?
4 3 Call: indomain(_1054) ?
4 3 Exit: indomain(1) ?
5 3 Call: xlabeling([_1085]) ?
6 4 Call: indomain(_1085) ?
6 4 Exit: indomain(1) ?
7 4 Call: xlabeling([]) ?
7 4 Exit: xlabeling([]) ?
5 3 Exit: xlabeling([1]) ?
3 2 Exit: xlabeling([1,1]) ?
1 1 Exit: goal(1,1) ?
X = 1,
Y = 1 ? ;
1 1 Redo: goal(1,1) ?
3 2 Redo: xlabeling([1,1]) ?
5 3 Redo: xlabeling([1]) ?
6 4 Redo: indomain(1) ?
6 4 Exit: indomain(2) ?
8 4 Call: xlabeling([]) ?
8 4 Exit: xlabeling([]) ?
5 3 Exit: xlabeling([2]) ?
3 2 Exit: xlabeling([1,2]) ?
1 1 Exit: goal(1,2) ?
X = 1,
Y = 2 ? ;
......
t(X,Y,Z) :-
domain([X,Y,Z], 1,4),
X#>Y, Y#>Z,
xlabeling([X,Y,Z]).
| ?- t(X,Y,Z).
X = 3,
Y = 2,
Z = 1 ? ;
X = 4,
Y = 2,
Z = 1 ? ;
X = 4,
Y = 3,
Z = 1 ? ;
X = 4,
Y = 3,
Z = 2 ? ;
no
To see the effect of domain reduction, I inserted some comments in the
following trace.
| ?- t(X,Y,Z).
1 1 Call: t(_181,_201,_221) ?
2 2 Call: domain([_181,_201,_221],1,4) ?
2 2 Exit: domain([_1135,_1166,_1197],1,4) ?
C: domains reduced to D(X) = [3,4]
D(Y) = [2,3]
D(Z) = [1,2]
3 2 Call: xlabeling([_1135,_1166,_1197]) ?
4 3 Call: indomain(_1135) ?
4 3 Exit: indomain(3) ?
C: The reduction above explains why we get 3 for X first,
(1 and 2 have been removed from the domain of X)
C: Once X instantiated to 3, we get further domain reduction
so that D(Y)=[2] and D(Z)=[1].
5 3 Call: xlabeling([2,1]) ?
6 4 Call: indomain(2) ?
6 4 Exit: indomain(2) ?
7 4 Call: xlabeling([1]) ?
8 5 Call: indomain(1) ?
8 5 Exit: indomain(1) ?
9 5 Call: xlabeling([]) ?
9 5 Exit: xlabeling([]) ?
7 4 Exit: xlabeling([1]) ?
5 3 Exit: xlabeling([2,1]) ?
3 2 Exit: xlabeling([3,2,1]) ?
1 1 Exit: t(3,2,1) ?
X = 3,
Y = 2,
Z = 1 ?