![]() | Projects |
People |
Papers |
Programs |
Teaching |
Links |
Brief Tutorial: Non-technical / Technical This page has been translated into French by Natalie Harmann (cache) |
|
Constraint satisfaction is a decision problem that involves finite choices.
It is ubiquitous.
For example, a transportation company may have to deliver to various locations within time windows specified by customers.
An airline company has to schedule its crews to serve different flights, satisfying constraints defined by the management and the unions.
The well known puzzle Sudoku is a
constraint satisfaction problem.
AutoCollage
(by Mirosoft Research)
is a fine example of constraint application to image processing.
Constraints shield solutions from a problem solver.
However, if used properly, constraints can also guide problem solvers to solutions.
This echoes teaching in
Daoism:
use the force.
A wide range of techniques have been applied to constraint
satisfaction. This includes constraint propagation, optimization, heuristics,
complete search and local search methods such as
guided local search,
neural network and
evolutionary computation.
For a brief explanation on what a Constraint Satisfaction Problem is, see brief tutorial (one page). For a slightly more technical introduction, see A glimpse of constraint satisfaction (14 pages). To learn the technology in depth, take my module Constraint Satisfaction for Decision Making.
More tutorial materials can be found in
CP4.
To learn more about the field, consult Rossi, van Beek & Walsh (ed),
Handbook of Constraint Programming,
Elsevier 2006,
E.P.K. Tsang, Foundations of Constraint Satisfaction, Academic Press, London, 1993,
E.C. Freuder & A. Mackworth (ed.), Constraint-based Reasoning, MIT Press, 1994,
R. Dechter, Constraint Processing,
Morgan Kaufmann, 2003, Journal of CONSTRAINTS
and research articles in recent journals and conference proceedings.
To get to know more about other researchers, visit other sites in the well
organized Constraint Archives or our
Links to other WWW Pages.
Related research: Computational Finance and Economics