Constraint satisfaction problem: Difference between revisions

Revision as of 07:43, 27 October 2023

Revision as of 07:43, 27 October 2023

Line 1:

Kakqqk{{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.

of static CSPs, each one a transformation of the previous one in which variables and constraints can be added (restriction) or removed (relaxation). Information found in the initial formulations of the problem can be used to refine the next ones. The solving method can be classified according to the way in which information is transferred:

Examples of problems that can be modeled as a constraint satisfaction problem include:

* [[Type inference]]<ref>Chandra, Satish, et al. "[https://cs.drexel.edu/~csgordon/papers/oopsla16.pdf Type inference for static compilation of JavaScript]." ACM SIGPLAN Notices 51.10 (2016): 410-429.</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>Farhi, Edward and Harrow, Aram. "[https://arxiv.org/abs/1602.07674 Quantum Supremacy through the Quantum Approximate Optimization Algorithm]." arXiv:1602.07674

</ref>

* [[Sudoku]], [[crossword]]s, [[futoshiki]], [[Kakuro]] (Cross Sums), [[Numbrix]]/[[Hidato]] 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.

==Formal definition==

Formally, a constraint satisfaction problem is defined as a triple <math>\langle X,D,C \rangle</math>, where <ref name=Russell2010>{{cite book|author1=Stuart Jonathan Russell |author2=Peter Norvig |title=Artificial Intelligence: A Modern Approach|date=2010|publisher=Prentice Hall|isbn=9780136042594|page=Chapter 6}}</ref>

* <math>X = \{X_1, \ldots,X_n\}</math> is a set of variables,

* <math>D = \{D_1, \ldots, D_n\}</math> is a set of their respective domains of values, and

* <math>C = \{C_1, \ldots, C_m\}</math> is a set of constraints.

Each variable <math>X_i</math> can take on the values in the nonempty ___domain <math>D_i</math>.

Every constraint <math>C_j \in C</math> is in turn a pair <math>\langle t_j,R_j \rangle</math>, where <math>t_j \subseteq X</math> is a subset of <math>k</math> variables and <math>R_j</math> is a <math>k</math>-ary [[relation (mathematics)|relation]] on the corresponding subset of domains <math>D_j</math>. An ''evaluation'' of the variables is a function from a subset of variables to a particular set of values in the corresponding subset of domains. An evaluation <math>v</math> satisfies a constraint <math>\langle t_j, R_j \rangle</math> if the values assigned to the variables <math>t_j</math> satisfy the relation <math>R_j</math>.

An evaluation is ''consistent'' if it does not violate any of the constraints. An evaluation is ''complete'' if it includes all variables. An evaluation is a ''solution'' if it is consistent and complete; such an evaluation is said to ''solve'' the constraint satisfaction problem.

==Solution==

Constraint satisfaction problems on finite domains are typically solved using a form of [[Search algorithm|search]]. The most used techniques are variants of [[backtracking]], [[constraint propagation]], and [[Local search (optimization)|local search]]. These techniques are also often combined, as in the [[Very large-scale neighborhood search|VLNS]] method, and current research involves other technologies such as [[linear programming]].<ref>{{Cite book|title=Hybrid optimization : the ten years of CPAIOR|date=2011|publisher=Springer|others=Milano, Michela., Van Hentenryck, Pascal., International Conference on Integration of AI and OR Techniques in Constraint Programming for Combinatorial Optimisation Problems.|isbn=9781441916440|___location=New York|oclc=695387020}}</ref>

[[Backtracking]] is a recursive algorithm. It maintains a partial assignment of the variables. Initially, all variables are unassigned. At each step, a variable is chosen, and all possible values are assigned to it in turn. For each value, the consistency of the partial assignment with the constraints is checked; in case of consistency, a [[Recursion|recursive]] call is performed. When all values have been tried, the algorithm backtracks. In this basic backtracking algorithm, consistency is defined as the satisfaction of all constraints whose variables are all assigned. Several variants of backtracking exist. [[Backmarking]] improves the efficiency of checking consistency. [[Backjumping]] allows saving part of the search by backtracking "more than one variable" in some cases. [[Constraint learning]] infers and saves new constraints that can be later used to avoid part of the search. [[Look-ahead (backtracking)|Look-ahead]] is also often used in backtracking to attempt to foresee the effects of choosing a variable or a value, thus sometimes determining in advance when a subproblem is satisfiable or unsatisfiable.

[[Constraint propagation]] techniques are methods used to modify a constraint satisfaction problem. More precisely, they are methods that enforce a form of [[local consistency]], which are conditions related to the consistency of a group of variables and/or constraints. Constraint propagation has various uses. First, it turns a problem into one that is equivalent but is usually simpler to solve. Second, it may prove satisfiability or unsatisfiability of problems. This is not guaranteed to happen in general; however, it always happens for some forms of constraint propagation and/or for certain kinds of problems. The most known and used forms of local consistency are [[arc consistency]], [[hyper-arc consistency]], and [[path consistency]]. The most popular constraint propagation method is the [[AC-3 algorithm]], which enforces arc consistency.

[[Local search (optimization)|Local search]] methods are incomplete satisfiability algorithms. They may find a solution of a problem, but they may fail even if the problem is satisfiable. They work by iteratively improving a complete assignment over the variables. At each step, a small number of variables are changed in value, with the overall aim of increasing the number of constraints satisfied by this assignment. The [[min-conflicts algorithm]] is a local search algorithm specific for CSPs and is based on that principle. In practice, local search appears to work well when these changes are also affected by random choices. An integration of search with local search has been developed, leading to [[Hybrid algorithm (constraint satisfaction)|hybrid algorithms]].

==Theoretical aspects==

===Decision problems===

{{Outdated as of|year=2017}}

CSPs are also studied in [[computational complexity theory]] and [[finite model theory]]. An important question is whether for each set of relations, the set of all CSPs that can be represented using only relations chosen from that set is either in [[P (complexity)|P]] or [[NP-complete]]. If such a [[dichotomy]] theorem is true, then CSPs provide one of the largest known subsets of [[NP (complexity)|NP]] which avoids [[NP-intermediate]] problems, whose existence was demonstrated by [[Ladner's theorem]] under the assumption that [[P versus NP problem|P ≠ NP]]. [[Schaefer's dichotomy theorem]] handles the case when all the available relations are [[Boolean operator (Boolean algebra)|Boolean operator]]s, that is, for ___domain size 2. Schaefer's dichotomy theorem was recently generalized to a larger class of relations.<ref>{{Cite book| last1 = Bodirsky | first1 = Manuel| last2 = Pinsker | first2 = Michael| doi = 10.1145/1993636.1993724 | contribution = Schaefer's theorem for graphs | publisher= [[Association for Computing Machinery]]| title = Proceedings of the 43rd Annual Symposium on Theory of Computing (STOC '11)| pages = 655–664 | year = 2011 | isbn = 978-1-4503-0691-1| arxiv = 1011.2894| bibcode = 2010arXiv1011.2894B| title-link = Symposium on Theory of Computing| s2cid = 47097319}}</ref>

Most classes of CSPs that are known to be tractable are those where the [[hypergraph]] of constraints has bounded [[treewidth]] (and there are no restrictions on the set of constraint relations), or where the constraints have arbitrary form but there exist essentially non-unary polymorphisms{{Clarify|date=February 2009}} of the set of constraint relations.

Every CSP can also be considered as a [[conjunctive query]] containment problem.<ref>{{Cite journal| last1 = Kolaitis| first1 = Phokion G.| last2 = Vardi| first2 = Moshe Y.| author-link2 = Moshe Y. Vardi| title = Conjunctive-Query Containment and Constraint Satisfaction| journal = [[Journal of Computer and System Sciences]]| volume = 61| issue = 2| pages = 302–332| year = 2000| doi = 10.1006/jcss.2000.1713 | doi-access = free}}</ref>

===Function problems===

A similar situation exists between the functional classes [[FP (complexity)|FP]] and [[Sharp-P|#P]]. By a generalization of [[Ladner's theorem]], there are also problems in neither FP nor [[Sharp-P-complete|#P-complete]] as long as FP ≠ #P. As in the decision case, a problem in the #CSP is defined by a set of relations. Each problem takes a [[Boolean logic|Boolean]] formula as input and the task is to compute the number of satisfying assignments. This can be further generalized by using larger ___domain sizes and attaching a weight to each satisfying assignment and computing the sum of these weights. It is known that any complex weighted #CSP problem is either in FP or #P-hard.<ref>{{Cite conference| last1 = Cai | first1 = Jin-Yi| last2 = Chen | first2 = Xi| doi = 10.1145/2213977.2214059 | title = Complexity of counting CSP with complex weights | book-title = [[Symposium on Theory of Computing|Proceedings of the Forty-Fourth Annual ACM Symposium on Theory of Computing (STOC '12)]] | pages = 909–920 | year = 2012 | isbn = 978-1-4503-1245-5| arxiv = 1111.2384| s2cid = 53245129}}</ref>

==Variants==

The classic model of Constraint Satisfaction Problem defines a model of static, inflexible constraints. This rigid model is a shortcoming that makes it difficult to represent problems easily.<ref>{{cite thesis

| first = Ian | last = Miguel

| date= July 2001 | title = Dynamic Flexible Constraint Satisfaction and its Application to AI Planning

| publisher = [[University of Edinburgh School of Informatics]]

| degree = Ph.D.

| hdl=1842/326

| citeseerx=10.1.1.9.6733

}}

</ref> Several modifications of the basic CSP definition have been proposed to adapt the model to a wide variety of problems.

===Dynamic CSPs===

'''Dynamic CSPs'''<ref>Dechter, R. and Dechter, A., [http://www.ics.uci.edu/%7Ecsp/r5.pdf Belief Maintenance in Dynamic Constraint Networks] {{Webarchive|url=https://web.archive.org/web/20121117042241/http://www.ics.uci.edu/%7Ecsp/r5.pdf |date=2012-11-17 }} In Proc. of AAAI-88, 37–42.</ref> (''DCSP''s) are useful when the original formulation of a problem is altered in some way, typically because the set of constraints to consider evolves because of the environment.<ref>[http://www.aaai.org/Papers/AAAI/1994/AAAI94-302.pdf Solution reuse in dynamic constraint satisfaction problems], Thomas Schiex</ref> DCSPs are viewed as a sequence of static CSPs, each one a transformation of the previous one in which variables and constraints can be added (restriction) or removed (relaxation). Information found in the initial formulations of the problem can be used to refine the next ones. The solving method can be classified according to the way in which information is transferred:

* [[Oracle machine|Oracles]]: the solution found to previous CSPs in the sequence are used as heuristics to guide the resolution of the current CSP from scratch.

* Local repair: each CSP is calculated starting from the partial solution of the previous one and repairing the inconsistent constraints with [[Local search (optimization)|local search]].