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 ?
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.
modeled like a Constraint Satisfaction Problem (CSP).
This allows them to derive a corresponding constraint satisfaction problem, which can be used directly for debugging.
For a large number of random Boolean constraint satisfaction problems, such as random k-SAT, we study how the number of locally maximal solutions evolves when constraints are added.
ABSTRACT; A feasible exam timetable is generated using a method based on constraint satisfaction and heuristics.
This puzzle is actually an instance of what is known in AI as a constraint satisfaction problem (CSP).
00--In this ambitious book, Paul Thagard develops a theory of coherence as constraint satisfaction that is precise enough to be stated formally, yet general enough to have application to an array of philosophical problems.
Our interest is to define evolutionary algorithms to solve Constraint Satisfaction Problems (CSP), which include benefits of traditional resolution methods of CSPs as well as inherent characteristics of these kind of problems.
This book focuses on constraint satisfaction problems related to tree partitioning problems enriched by several additional constraints that restrict the possible partitions topology.
The 32 papers accepted for the August 2012 symposium present new developments in machine learning, data mining, constraint satisfaction problems, belief propagation, logic and reasoning, multi-agent systems, and games.
Optimal long code testing with one free bit, constraint satisfaction problems of bounded width, symmetry and approximability of submodular maximization problems, smoothed analysis of multiobjective optimization, and distance oracles for sparse graphs are some other areas explored.

Full browser ?