What is Constraint Satisfaction?

A quick tutorial, by Edward Tsang

A standard Constraint Satisfaction Problem (CSP) is a finite-choices decision problem where one is given a fixed set of decisions to make. Each decision involves choosing among a fixed set of options. Each constraint restricts the combination of choices that can be taken simultaneously. The task is to make all the decisions such that all the constraints are satisfied. Many real life problems, such as planning, scheduling and timetabling can be formalised as constraint satisfaction problems. Very efficient algorithms have been developed for solving constraint satisfaction problems (by exploiting their characteristics). Constraint programming is a multi-million Dollars business.

In CSPs where some solutions are better than others, one may be asked to find the optimal solution according to a specific objective function. In CSPs where no solutions exist, one may be asked to find the "best" near-solutions according to a specific objective function (e.g. to violate the least number of constraints).

Some of the fundamental topics in constraint satisfaction include:

Algorithms for solving CSPs
including complete search algorithms and stochastic algorithms for satisfiability as well as optimization problems
Theorectical aspects of CSPs
e.g. how to recognize tractable CSPs? how to characterise CSPs, e.g. measuring the tightness of CSPs?
Software engineering aspects of constraint programming
e.g. how to formulate algorithms? how to map CSPs to algorithms?
Applications of CSPs
e.g. industrial scheduling, resource allocation, agents

To learn more about the field, follow a longer tutorial, or E.P.K. Tsang, Foundations of Constraint Satisfaction, Academic Press, London, 1993, E.C. Freuder & A. Mackworth (ed.), Constraint-based Reasoning, MIT Press, 1994, Journal of CONSTRAINTS and research articles in recent journals and conference proceedings. To get to know more about other researchers in the field, visit other sites in the well organized Constraint Archives following our Links to other WWW Pages.

(Download and install the 8-Queens Demo to see an example constraint satisfaction problem and constraint techniques in action.)

This page is maintained by:
Edward Tsang, e-mail edward at domain 'essex.ac.uk'

Last Updated: 20 October 1998 (revised 17 January 2005)

Constraint Satisfaction Home Page (http://cswww.essex.ac.uk/CSP)