constraint satisfaction


Also found in: Wikipedia.

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).
References in periodicals archive ?
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.
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.
The maintenance planning problem is basically a constraint satisfaction problem for which [4] gives a good background.
Coordinated Management of Large-Scale Networks Using Constraint Satisfaction.
The present work proposes a constraint satisfaction model for the problem of programming university courses for the Faculty of Chemical Sciences and Engineering (FCSE).
In this investigation, we focus on analyzing the relation between instances and heuristics for constraint satisfaction problem (CSP), which is one of the most studied combinatorial problems in the literature.
Section 2 provides an introduction to the main principles of constraint satisfaction problem.
Hopfield networks can also solve constraint satisfaction problems.
The problem of determining the possible equilibria reached in a competitive electricity market, with strategic generators influencing the market's clearance price, can be represented as a combinatorial problem or a constraint satisfaction problem (CSP).
Constraint satisfaction problems; CSP formalisms and techniques.
A few examples of specific topics include text detection in urban scenes, collaborative agent-based learning for brain tumor diagnosis, coherence as an inclusive notion of rationality, stability of solution in constraint satisfaction problems, and neuro-fuzzy approach for the characterization of building materials.
We use the efficiency of both Semantic Web technologies and logic programming in modeling the problem of group formation as a constraint satisfaction problem (Kumar, 1992).

Full browser ?