constraint satisfaction

application The process of assigning values to variables

while meeting certain requirements or "constraints". For

example, in graph colouring, a node is a variable, the

colour assigned to it is its value and a link between two

nodes represents the constraint that those two nodes must not

be assigned the same colour. In scheduling, constraints

apply to such variables as the starting and ending times for

tasks.

The Simplex method is one well known technique for solving

numerical constraints.

The search difficulty of constraint satisfaction problems can

be determined on average from knowledge of easily computed

structural properties of the problems. In fact, hard

instances of NP-complete problems are concentrated near an

abrupt transition between under- and over-constrained

problems. This transition is analogous to phase transitions

in physical systems and offers a way to estimate the likely

difficulty of a constraint problem before attempting to solve

it with search.

Phase transitions in search (Tad

Hogg, XEROX PARC).

(1995-02-15)