Constraint Programming
by Krzysztof R. Apt
The central notion in the area of constraint programming is a constraint satisfaction problem (CSP). A CSP consists of a finite set of constraints, which are simply relations over some domains. The task of constraint programming consists of formulating the initial problem as a CSP and of solving it by means of general or domain specific methods. ‘Solving’ can mean finding a solution, all solutions or the best solution with respect to some quality measure.
The general methods are usually concerned with techniques of reducing the search space and with specific search methods. The main idea is to reduce a given CSP to another one that is equivalent (i.e., has the same set of solutions) but is easier to solve. This process is called constraint propagation and the algorithms that achieve such a reduction are called constraint propagation algorithms. So these algorithms reduce the search space and consequently attempt to limit the combinatorial explosion. Which type of constraint propagation is used depends on the initial choice of constraints and domains and on the applications. In practice several different constraint propagation algorithms were proposed.
In contrast, the domain specific methods are usually provided in the form of special purpose algorithms or specialised packages, usually called constraint solvers. Typical examples of constraint solvers are:
• a program that solves systems of linear equations
• a package for linear programming
• an implementation of the unification algorithm, a cornerstone of automated theorem proving.
This distinction between the general and domain specific methods is crucial and one needs to keep it in mind when studying constraint programming so that one does not apply general methods when efficient special purpose techniques are available. This distinction naturally calls for systems for constraint programming in which both the general and the domain specific methods are available. The former are usually present in the form of a built-in constraint propagation for a selected type of constraints and of specific constructs that support search, while the latter are often present in the form of various built-ins that allow one to call directly specific constraint solvers.
Problems that can be solved in a natural way by means of constraint programming are usually those for which efficient algorithms are lacking (for example computationally intractable problems) or for which formalization in terms of laws (for example electrical engineering problems) leads to a more flexible style of programming in which the dependencies between the relevant variables can be expressed in the most general form.
In fact, many computational problems are not precisely defined or their precise specification may depend on such factors as the time limit required for the generation of a solution. When solving such problems one usually needs to proceed by several iterations. Modelling these problems by means of constraints can be often beneficial. Indeed, the appropriate modification of the program can then be often taken care of by modification of some constraints or by altering an appropriate fixed program component, for example the one that defines the adopted search method.
An additional aspect brought in by constraint programming is that modelling by means of constraints leads to a representation by means of relations. In a number of circumstances this representation allows us to use the same program for different purposes. This can be useful in several cases, for instance when trying to figure out which input led to a given output. In conventional programming languages relations have to be converted first to functions and this possibility is then lost.
The use of relations as a basis for problem formulation bears some resemblance to database systems, for instance relational databases. The difference is that in database systems such relations (tables) are usually explicitly given and the task consists of efficiently querying them, while in constraint programming these relations (for instance equations) are given implicitly and the task consists of solving them.
We can summarize the above mentioned characteristics of constraint programming as follows:
• the programming process consists of two phases: a generation of a problem representation as a CSP, and a solution of it; in practice, both phases can consist of several smaller steps and can be interleaved
• the representation of a problem by means of constraints is very flexible because the constraints can be added, removed or modified
• the use of relations to represent constraints blurs the difference between input and output. This makes it possible to use the same program for a number of purposes.
The ERCIM Working Group on Constraints was founded in the fall of 1996 in order to facilitate the dissemination of knowledge in the area of Constraint Programming between the ERCIM researchers. In the meantime it comprises 14 ERCIM institutes. This shows substantial interest in this field.
The research within the group led to a number of scientific collaborations among members of different institutes and to a couple of joint research initiatives. So far three scientific meetings took place. The fourth one will take place this October on Cyprus. In April this year the group shared with two other ERCIM Working Groups the ERCIM award.
In the field of Constraint Programming techniques from Artificial Intelligence, Operations Research and Mathematical Logic are often combined. This leads to exciting new challenges. In particular, an ongoing research challenge consists in finding efficient constraint propagation algorithms that are tailored to specific constraints (such as the ones used for representing scheduling problems). On the programming side there is a continuing need to design and implement better constraint programming languages and environments. On the applications side one keeps finding new applications for this style of programming. Interesting recent examples include computer music and virtual reality applications.
Links:
Working Group on Constraints: http://www.cwi.nl/projects/ercim-wg.html
Please contact:
Krzysztof R. Apt - CWI
Tel: +31 20 592 4135
E-mail: apt@cwi.nl