Projects | People | Papers | Programs | Teaching | Links | Brief Tutorial: Non-technical / Technical This page has been translated into French by Natalie Harmann (cache)

Sponsors:

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