Not to be confused with Communicating sequential processes.
This article needs additional citations for verification. Please help improve this article by adding citations to reliable sources. Unsourced material may be challenged and removed. Find sources: "Constraint satisfaction problem" – news · newspapers · books · scholar · JSTOR(November 2014) (Learn how and when to remove this message)
Constraint satisfaction problems (CSPs) are mathematical questions defined as a set of objects whose state must satisfy a number of constraints or limitations. CSPs represent the entities in a problem as a homogeneous collection of finite constraints over variables, which is solved by constraint satisfaction methods. CSPs are the subject of research in both artificial intelligence and operations research, since the regularity in their formulation provides a common basis to analyze and solve problems of many seemingly unrelated families. CSPs often exhibit high complexity, requiring a combination of heuristics and combinatorial search methods to be solved in a reasonable time. Constraint programming (CP) is the field of research that specifically focuses on tackling these kinds of problems.[1][2] Additionally, the Boolean satisfiability problem (SAT), satisfiability modulo theories (SMT), mixed integer programming (MIP) and answer set programming (ASP) are all fields of research focusing on the resolution of particular forms of the constraint satisfaction problem.
Examples of problems that can be modeled as a constraint satisfaction problem include:
Type inference[3][4]
Eight queens puzzle
Map coloring problem
Maximum cut problem[5]
Sudoku, crosswords, futoshiki, Kakuro (Cross Sums), Numbrix/Hidato and many other logic puzzles
These are often provided with tutorials of CP, ASP, Boolean SAT and SMT solvers. In the general case, constraint problems can be much harder, and may not be expressible in some of these simpler systems. "Real life" examples include automated planning,[6][7] lexical disambiguation,[8][9] musicology,[10] product configuration[11] and resource allocation.[12]
The existence of a solution to a CSP can be viewed as a decision problem. This can be decided by finding a solution, or failing to find a solution after exhaustive search (stochastic algorithms typically never reach an exhaustive conclusion, while directed searches often do, on sufficiently small problems). In some cases the CSP might be known to have solutions beforehand, through some other mathematical inference process.
^Lecoutre, Christophe (2013). Constraint Networks: Techniques and Algorithms. Wiley. p. 26. ISBN 978-1-118-61791-5.
^"Constraints – incl. option to publish open access". springer.com. Retrieved 2019-10-03.
^Chandra, Satish, et al. "Type inference for static compilation of JavaScript." ACM SIGPLAN Notices 51.10 (2016): 410-429.
^Jim, Trevor, and Jens Palsberg. "Type inference in systems of recursive types with subtyping." Available on authors' web page (1999).
^Farhi, Edward and Harrow, Aram. "Quantum Supremacy through the Quantum Approximate Optimization Algorithm." arXiv:1602.07674
^Malik Ghallab; Dana Nau; Paolo Traverso (21 May 2004). Automated Planning: Theory and Practice. Elsevier. pp. 1–. ISBN 978-0-08-049051-9.
^Dynamic Flexible Constraint Satisfaction and Its Application to AI Planning, Archived 2009-02-06 at the Wayback Machine Ian Miguel – slides.
^Demetriou, George C. "Lexical disambiguation using constraint handling in Prolog (CHIP)." Proceedings of the sixth conference on European chapter of the Association for Computational Linguistics. Association for Computational Linguistics, 1993.
^MacDonald, Maryellen C., and Mark S. Seidenberg. "Constraint satisfaction accounts of lexical and sentence comprehension." Handbook of Psycholinguistics (Second Edition). 2006. 581–611.
^Mauricio Toro, Carlos Agon, Camilo Rueda, Gerard Assayag. "GELISP: A FRAMEWORK TO REPRESENT MUSICAL CONSTRAINT SATISFACTION PROBLEMS AND SEARCH STRATEGIES." Journal of Theoretical and Applied Information Technology 86 (2). 2016. 327–331.
^Applying constraint satisfaction approach to solve product configuration problems with cardinality-based configuration rules, Dong Yang & Ming Dong, Journal of Intelligent Manufacturing volume 24, pages99–111 (2013)
^Modi, Pragnesh Jay, et al. "A dynamic distributed constraint satisfaction approach to resource allocation." International Conference on Principles and Practice of Constraint Programming. Springer, Berlin, Heidelberg, 2001.
and 22 Related for: Constraint satisfaction problem information
Constraintsatisfactionproblems (CSPs) are mathematical questions defined as a set of objects whose state must satisfy a number of constraints or limitations...
intelligence and operations research, constraintsatisfaction is the process of finding a solution through a set of constraints that impose conditions that the...
dual problem is a reformulation of a constraintsatisfactionproblem expressing each constraint of the original problem as a variable. Dual problems only...
Weighted ConstraintSatisfactionProblem (WCSP) is a generalization of a constraintsatisfactionproblem (CSP) where some of the constraints can be violated...
Constraint programming (CP) is a paradigm for solving combinatorial problems that draws on a wide range of techniques from artificial intelligence, computer...
classes of constraintsatisfactionproblems on finite domains. Solving a constraintsatisfactionproblem on a finite domain is an NP-complete problem in general...
The constrained-optimization problem (COP) is a significant generalization of the classic constraint-satisfactionproblem (CSP) model. COP is a CSP that...
expression of an important class of constraintsatisfactionproblems, such as certain scheduling or frequency assignment problems. The fact that homomorphisms...
algorithms for finding solutions to some computational problems, notably constraintsatisfactionproblems, that incrementally builds candidates to the solutions...
computer science Constraintsatisfactionproblem Loading gauge, a constraint in engineering Optimality theory, in linguistics, a constraint-based theory which...
hypergraphs are used to represent relations among constraints in a constraintsatisfactionproblem. A constraint graph is a special case of a factor graph, which...
of constraints over the variables is minimized. Distributed ConstraintSatisfaction is a framework for describing a problem in terms of constraints that...
{\displaystyle {\mathcal {S}}} . The exact cover problem to find an exact cover is a kind of constraintsatisfactionproblem. The elements of S {\displaystyle {\mathcal...
operations research, hierarchical constraintsatisfaction (HCS) is a method of handling constraintsatisfactionproblems where the variables have large domains...
In constraintsatisfaction, local consistency conditions are properties of constraintsatisfactionproblems related to the consistency of subsets of variables...
transformation reformulates a constraintsatisfactionproblem in such a way all constraints have at most two variables. The new problem is satisfiable if and...
benchmark in the evaluation of computer algorithms for solving constraintsatisfactionproblems. The following version of the puzzle appeared in Life International...
minimum satisfiability problem. The MAX-SAT problem can be extended to the case where the variables of the constraintsatisfactionproblem belong to the set...
weighted constraintsatisfactionproblem. Developed and introduced by Satish Kumar Thittamaranahalli (T. K. Satish Kumar), the idea of the constraint composite...
include concepts from constraint satisfaction. A constraint logic program is a logic program that contains constraints in the body of clauses. An example...
problems that are polynomially-bounded. Assignment problem Bin packing problem Closure problemConstraintsatisfactionproblem Cutting stock problem Dominating...