Editing Constraint satisfaction problem (section)

{{Short description|Set of objects whose state must satisfy limits}}
{{distinguish|Communicating sequential processes}}
{{more citations needed|date=November 2014}}
'''Constraint satisfaction problems''' ('''CSPs''') are mathematical questions defined as a set of objects whose [[State (computer science)|state]] must satisfy a number of [[Constraint (mathematics)|constraints]] or [[Limit (mathematics)|limitations]]. CSPs represent the entities in a problem as a homogeneous collection of finite constraints over [[Variable (mathematics)|variable]]s, 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. [[Complexity of constraint satisfaction|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.<ref>{{Cite book|title=Constraint Networks: Techniques and Algorithms|last=Lecoutre|first=Christophe|publisher=Wiley|year=2013|isbn=978-1-118-61791-5|pages=26}}</ref><ref>{{Cite web|url=http://www.springer.com/computer/ai/journal/10601|title=Constraints – incl. option to publish open access|website=springer.com|language=en|access-date=2019-10-03}}</ref> 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]]<ref>{{cite book |chapter-url=https://cs.drexel.edu/~csgordon/papers/oopsla16.pdf |doi=10.1145/2983990.2984017 |chapter=Type inference for static compilation of JavaScript |title=Proceedings of the 2016 ACM SIGPLAN International Conference on Object-Oriented Programming, Systems, Languages, and Applications |date=2016 |last1=Chandra |first1=Satish |last2=Gordon |first2=Colin S. |last3=Jeannin |first3=Jean-Baptiste |last4=Schlesinger |first4=Cole |last5=Sridharan |first5=Manu |last6=Tip |first6=Frank |last7=Choi |first7=Youngil |pages=410–429 |isbn=978-1-4503-4444-9 }}</ref><ref>Jim, Trevor, and Jens Palsberg. "[http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.78.886&rep=rep1&type=pdf Type inference in systems of recursive types with subtyping]." Available on authors' web page (1999).</ref>
* [[Eight queens puzzle]]
* [[Graph coloring|Map coloring problem]]
* [[Maximum cut|Maximum cut problem]]<ref>{{Cite arXiv |eprint=1602.07674 |last1=Farhi |first1=Edward |author2=Aram W Harrow |title=Quantum Supremacy through the Quantum Approximate Optimization Algorithm |date=2016 |class=quant-ph }}</ref>
* [[Sudoku]], [[crossword]]s, [[futoshiki]], [[Kakuro]] (Cross Sums), [[Numbrix]]/[[Hidato]], [[Zebra Puzzle]], and many other [[logic puzzle]]s

These are often provided with tutorials of [[Constraint programming|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]],<ref name="GhallabNau2004">{{cite book|author1=Malik Ghallab|author2=Dana Nau|author3=Paolo Traverso|title=Automated Planning: Theory and Practice|url=https://books.google.com/books?id=uYnpze57MSgC&q=%22constraint+satisfaction%22&pg=PP1|date=21 May 2004|publisher=Elsevier|isbn=978-0-08-049051-9|pages=1–}}</ref><ref>[http://www.cs.st-andrews.ac.uk/~ianm/docs/Thesis.ppt Dynamic Flexible Constraint Satisfaction and Its Application to AI Planning], {{webarchive|url=https://web.archive.org/web/20090206055207/http://www.cs.st-andrews.ac.uk/~ianm/docs/Thesis.ppt |date=2009-02-06 }} Ian Miguel – slides.</ref> [[lexical disambiguation]],<ref>Demetriou, George C. "[http://www.aclweb.org/anthology/E93-1051 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.</ref><ref>MacDonald, Maryellen C., and Mark S. Seidenberg. "[https://web.archive.org/web/20180325105726/https://pdfs.semanticscholar.org/a73e/53c44f1e998c5a03b9cbac9e0e16d5b09e77.pdf Constraint satisfaction accounts of lexical and sentence comprehension]." Handbook of Psycholinguistics (Second Edition). 2006. 581–611.</ref> [[musicology]],<ref>Mauricio Toro, Carlos Agon, Camilo Rueda, Gerard Assayag. "[http://www.jatit.org/volumes/Vol86No2/17Vol86No2.pdf GELISP: A FRAMEWORK TO REPRESENT MUSICAL CONSTRAINT SATISFACTION PROBLEMS AND SEARCH STRATEGIES]." Journal of Theoretical and Applied Information Technology 86 (2). 2016. 327–331.</ref> [[Configure, price and quote|product configuration]]<ref>''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)</ref> and [[resource allocation]].<ref>Modi, Pragnesh Jay, et al. "[http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.24.8697&rep=rep1&type=pdf A dynamic distributed constraint satisfaction approach to resource allocation]." International Conference on Principles and Practice of Constraint Programming. Springer, Berlin, Heidelberg, 2001.</ref>

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 algorithm]]s 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.