Constraint Satisfaction

Constraint satisfaction is a general framework for expressing many computational problems including scheduling, graph colouring, and vision processing. A Constraint Satisfaction Problem (CSP) consists of a domain, a number of variables and a number of constraints restricting combinations of values of the variables . A solution of a CSP is an assignment of a domain value to each variable which satisfies all the constraints simultaneously. A constraint problem can have many mutually conflicting constraints. For example suppose we have:

the finite domain {1,2,3,4,5,6};
three variables x,y,z;

and two constraints expressing that the sum of x,y must be 6 and that the product or y,z must be at least 20. There are only 5 solutions which satisfy both constraints:

x=1 , y=5 , z=4
x=1 , y=5 , z=5
x=1 , y=5 , z=6
x=2 , y=4 , z=5
x=2 , y=4 , z=6

One technique for solving constraint problems is to iterate through each possible solution checking if it satisfies each constraint. Such a solution technique has the disadvantage that the number of possible solutions grow exponentially with the number of variables.

Some constraint problems are inherently easy to solve. For example if each variable in the constraint is only constrained by at most two constraints and there are no cyclic dependencies, then the problem is easy to solve. The solution can be found by identifying a root node and assigning values in a backtrack free manner.

My current research in constraint satisfaction is in identifying algebraic conditions on constraint problems that make them easy to solve. Earlier work was done at Royal Hollow College where using techniques from universal algebra and database theory many tractable classes where identified. A summary can be found . Currently I am working on understanding the role of symmetry in solving CSPs.

Justin Pearson