Guide to Constraint Programming |
© Roman Barták, 1998 |
||
Contents | Next |
„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." | |
Dick Pountain, BYTE, February 1995 |
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 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)
- N-queens
- Zebra (five house puzzle)
- a crossword puzzle
- cryptoarithmetics (SEND+MORE=MONEY)
- mastermind
- graph coloring
- analysis and synthesis of analog circuits
- option trading analysis
- cutting stock
- DNA sequencing
- scheduling
- chemical hypothetical reasoning
- warehouse location
- forest treatment scheduling
- airport counter allocation (Cathay Pacific Airways Ltd)
- crew rostering problem (Italian Railway Company)
- well activity scheduling (Saga Petroleum a.s.)
Contents | Next | ||
Designed and maintained by Roman Barták |