application The process of assigning values to variables
while meeting certain requirements or "
constraints". For
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.
(1995-02-15)