constraint satisfaction

Also found in: Wikipedia.

constraint satisfaction

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).
This article is provided by FOLDOC - Free Online Dictionary of Computing (
References in periodicals archive ?
Evans and his colleagues used a concept from psychology called "parallel constraint satisfaction" theory to explain the effect they saw in the study.
They cover vision and robotics; logic, constraint satisfaction, and qualitative theory; classification and clustering; modeling; planning and recommender systems; and lexical knowledge representation and natural language processing.
Constraint satisfaction problems (CSPs) are combinatorial problems classified inside the NP-Complete class [1].
Many combinatorial problems such as scheduling and timetabling were then formulated in the form of constraint satisfaction problems (CSP).
It has been formulated to be a constraint satisfaction problem and solved by using the satisfiability modulo theory (SMT) [6].
The chip has fabrication on Intel's 14nm process tech; 130,000 neurons; 139 million synapses; a fully asynchronous neuromorphic many-core mesh supporting sparse, hierarchical, and recurrent neural network topologies, with neurons capable of communicating with each other; a programmable learning engine for each neuromorphic core; and development and testing of several algorithms for path planning, sparse coding, dictionary learning, constraint satisfaction, and dynamic pattern learning and adaptation.
Since the problem can be encoded into a constraint satisfaction problem, the main components that have to be identified are variables, domains, and constraints.
We therefore chose to formulate the problem as a constraint satisfaction problem because many of the requirements on the plan are naturally translated into constraints and also because Constraint Programming techniques has historically been successful for applications similar to this.
Among the latter we find constraint programming, which can also be divided into two branches: constraint satisfaction and constraint solving.
The constraint satisfaction problem (CSP) is the fundamental concept of constraint-based declarative environments [4, 9].
Section 2 provides an introduction to the main principles of constraint satisfaction problem.

Full browser ?