„Were you to ask me which programming paradigm is likely to gain most in
commercial significance over the next 5 years I'd have to pick Constraint Logic Programming (CLP), even though
it's perhaps currently one of the least known and understood."
Constraint programming is an emergent software technology for declarative
description and effective solving of large, particularly combinatorial, problems especially in areas of planning
and scheduling.
A bit of history ...
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.
... and some applications.
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.
Current research in this area deals with various foundational issues, with
implementation aspects and with new applications of constraint programming.
What is a constraint?
A constraint is simply a logical relation among several unknowns (or variables), each taking a value in a given
domain. A constraint thus restricts the possible values that variables can take, it represents some partial information
about the variables of interest. For instance, "the circle is inside the square" relates two objects
without precisely specifying their positions, i.e., their coordinates. Now, one may move the square or the circle
and he or she is still able to maintain the relation between these two objects. Also, one may want to add other
object, say triangle, and introduce another constraint, say "square is to the left of the triangle".
From the user (human) point of view, everything remains absolutely transparent.
Constraints naturally enjoy several interesting properties:
constraints may specify partial information, i.e., constraint need not uniquely specify the values of its variables,
constraints are non-directional, typically a constraint on (say) two variables X, Y can be used to infer a constraint
on X given a constraint on Y and vice versa,
constraints are declarative, i.e., they specify what relationship must hold without specifying a computational
procedure to enforce that relationship,
constraints are additive, i.e., the order of imposition of constraints does not matter, all that matters
at the end is that the conjunction of constraints is in effect,
constraints are rarely independent, typicaly constraints in the constraint store share variables.
Constraints arise naturally in most areas of human endeavor. The three angles
of a triangle sum to 180 degrees, the sum of the currents floating into a node must equal zero, the position of
the scroller in the window scrollbar must reflect the visible part of the underlying document, these are some examples
of constraints which appear in the real world. Thus, constraints are a natural medium for people to express problems
in many fields.
So, what does the constraint programming
deal with? Constraint programming is the study of computational systems based
on constraints. The idea of constraint programming is to solve problems by stating constraints (conditions, properties)
which must be satisfied by the solution.
Work in this area can be tracked back to research in Artificial Intelligence
and Computer Graphics in the sixties and seventies. Only in the last decade, however, has there emerged a growing
realization that these ideas provide the basis for a powerful approach to programming, modeling and problem solving
and that different efforts to exploit these ideas can be unified under a common conceptual and practical framework,
constraint programming.
Currently there can be seen two branches of Constraint Programming research
which arise from distinct bases and, thus, use different approaches to solve constraints.
Constraint Satisfaction
Constraint Satisfaction arose from the research in Artificial Intelligence (combinatorial problems, search) and
Computer Graphics (SKETCHPAD system, expressing geometric coherence in the case of scene analysis).
The Constraint Satisfaction Problem (CSP) is a problem where one is given:
a finite set of variables,
a function which maps every variable to a finite domain,
a finite set of constraints.
Each constraint restricts the combination of values that a set of variables
may take simultaneously. A solution of a CSP is an assignment to each variable a value from its domain satisfying
all the constraints. The task is to find one solution or all solutions.
Thus, the CSP is a combinatorial problem which can be solved by search.
There exists a trivial algorithm that solves such problems or finds that there is no solution. This algorithm generates
all possible combinations of values and, then, it tests whether the given combination of values satisfies all constraints
or not (consequently, this algorithm is called generate and test). Clearly, this algorithm takes a long time to run so the research in the area of
constraint satisfaction concentrate on finding algorithms which solve the problem more efficiently, at least for
a given subset of problems.
Constraint Solving
Constraint Solving differs from Constraint Satisfaction by using variables with infinite domains. Also, the individual
constraints are more complicated, e.g., nonlinear equalities. Consequently, the constraint solving algorithms uses
the algebraic and numeric methods instead of combinations and search. However, there exists an approach which discretizes
the infinite domain into finite number of components and, then, applies the techniques of constraint satisfaction.
Did you say practical applications?
This subsection is dedicated to those eager readers who want to see some examples of practical applications of
the constraint technology first, before diving into the subject.
Some corporations which exploit the advantages of constraint technology: British Airways, SAS, Swissair,
French railway authority SNCF, Hong Kong International Terminals, Michelin, Dassault etc.
puzzles (not really practical applications, but they are fun)
What is a constraint?
Constraint Satisfaction