Constraint Programming

What is 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.


             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.

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

           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.

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.

Constraint Satisfaction

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:

    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. 

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:

    -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. 

Example

Suppose we have variables X,Y,Z, and their domains are

              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.

Example

Using the 4-queen problem as an example, we can use a variable to represent each queen, thus we have 4 variables, say,

             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

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).


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

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.

Constraint Logic Programming: a Brief Introduction

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:

 
  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).

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.

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.

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:

:- use_module(library(clpr)). 

p(f(X)) :- {X>1}, q(X).
q(X) :- {X<5}.

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

   ?- 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.

Example.

:- 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.

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:

   -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.

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.

     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.

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]?

:- 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.)

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

:- 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.

It is important to understand how labeling works. Consider this program:

%--------------------------------------------------------------------
% 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.

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:

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 ? ;

......

That is, xlabeling generates all combinations of X and Y by backtracking.

Now, let's see the use of xlabeling with constraints.

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 ? 

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: