Constraint satisfaction problem: Difference between revisions

Revision as of 20:18, 3 February 2024

Latest revision as of 22:02, 19 June 2025

(27 intermediate revisions by 14 users not shown)

Line 6:

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

* [[Type inference]]<ref>Chandra, Satish,{{cite etbook al. "[|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 NoticesInternational 51.10Conference (2016):on 410Object-429Oriented 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 and|author2=Aram W Harrow, Aram. "[https://arxiv.org/abs/1602.07674 |title=Quantum Supremacy through the Quantum Approximate Optimization Algorithm]." arXiv:1602.07674|date=2016 |class=quant-ph }}</ref>

* [[Sudoku]], [[crossword]]s, [[futoshiki]], [[Kakuro]] (Cross Sums), [[Numbrix]]/[[Hidato]], [[Zebra Puzzle]], and many other [[logic puzzle]]s

</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>

Line 23 ⟶ 22:

* <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\{1, 2, \ldots, n\}</math> is a subsetset of <math>k</math> variablesindices and <math>R_j</math> is a <math>k</math>-ary [[relation (mathematics)|relation]] on the corresponding subsetproduct of domains <math>D_j\times_{i \in t_j} D_i</math> where the product is taken with indices in ascending order. 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 bookconference|title=Hybrid optimization : the ten years of CPAIOR|date=2011|publisher=Springer|otherseditor1=[[Michela Milano|Milano, Michela]], |editor1-link=Michela Milano |editor2=Van Hentenryck, Pascal., |conference=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.

Line 38 ⟶ 37:

==Theoretical aspects==

===DecisionComputational problemsComplexity===

CSPs are also studied in [[computational complexity theory]], [[finite model theory]] and [[universal algebra]]. It turned out that questions about the complexity of CSPs translate into important universal-algebraic questions about underlying algebras. This approach is known as the ''algebraic approach'' to CSPs.<ref>{{Cite journal |last1=Barto |first1=Libor |last2=Brady |first2=Zarathustra |last3=Bulatov |first3=Andrei |last4=Kozik |first4=Marcin |last5=Zhuk |first5=Dmitriy |date=2024-05-15 |title=Unifying the Three Algebraic Approaches to the CSP via Minimal Taylor Algebras |journal=Theoretics |volume=3 |pages=11361 |doi=10.46298/theoretics.24.14 |arxiv=2104.11808 |issn=2751-4838}}</ref>

CSPs are also studied in [[computational complexity theory]] and [[finite model theory]]. An important [[dichotomy]] theorem states that 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]]. CSPs thus 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 later 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> and the full dichotomy theorem was finally proved independently by Andrei Bulatov<ref>{{Cite book| last1 = Bulatov | first1 = Andrei | doi = 10.1109/FOCS.2017.37 | contribution = A Dichotomy Theorem for Nonuniform CSPs | publisher = IEEE Computer Society | title = Proceedings of the 58th IEEE Annual Symposium on Foundations of Computer Science, FOCS 2017 | pages = 319–330 | year = 2017}}</ref> and Dmitriy Zhuk.<ref>{{Cite journal| last1 = Zhuk | first1 = Dmitriy | doi = 10.1145/3402029 | title = A Proof of the CSP Dichotomy Conjecture | journal = Journal of the ACM | volume = 67 | number = 5 | pages = 1–78 | year = 2020| arxiv = 1704.01914 }}</ref>

Since every computational decision problem is [[Polynomial-time reduction|polynomial-time equivalent]] to a CSP with an infinite template,<ref>{{Cite book |last1=Bodirsky |first1=Manuel |last2=Grohe |first2=Martin |chapter=Non-dichotomies in Constraint Satisfaction Complexity |series=Lecture Notes in Computer Science |date=2008 |volume=5126 |editor-last=Aceto |editor-first=Luca |editor2-last=Damgård |editor2-first=Ivan |editor3-last=Goldberg |editor3-first=Leslie Ann |editor4-last=Halldórsson |editor4-first=Magnús M. |editor5-last=Ingólfsdóttir |editor5-first=Anna |editor6-last=Walukiewicz |editor6-first=Igor |title=Automata, Languages and Programming |chapter-url=https://link.springer.com/chapter/10.1007/978-3-540-70583-3_16 |language=en |___location=Berlin, Heidelberg |publisher=Springer |pages=184–196 |doi=10.1007/978-3-540-70583-3_16 |isbn=978-3-540-70583-3}}</ref> general CSPs can have arbitrary complexity. In particular, there are also CSPs within the class of [[NP-intermediate]] problems, whose existence was demonstrated by [[NP-intermediate|Ladner]], under the assumption that [[P versus NP problem|P ≠ NP]].

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.

However, a large class of CSPs arising from natural applications satisfy a complexity dichotomy, meaning that every CSP within that class is either in [[P (complexity)|P]] or [[NP-complete]]. These CSPs thus provide one of the largest known subsets of [[NP (complexity)|NP]] which avoids [[NP-intermediate]] problems. A complexity dichotomy was first proven by [[Schaefer's dichotomy theorem|Schaefer]] for Boolean CSPs, i.e. CSPs over a 2-element ___domain and where all the available relations are [[Boolean operator (Boolean algebra)|Boolean operator]]s. This result has been generalized for various classes of CSPs, most notably for all CSPs over finite domains. This ''finite-___domain dichotomy conjecture'' was first formulated by Tomás Feder and Moshe Vardi,<ref>{{Cite journal |last1=Feder |first1=Tomás |last2=Vardi |first2=Moshe Y. |author-link2=Moshe Vardi |date=1998 |title=The Computational Structure of Monotone Monadic SNP and Constraint Satisfaction: A Study through Datalog and Group Theory |url=http://epubs.siam.org/doi/10.1137/S0097539794266766 |journal=SIAM Journal on Computing |language=en |volume=28 |issue=1 |pages=57–104 |doi=10.1137/S0097539794266766 |issn=0097-5397|url-access=subscription }}</ref> and finally proven independently by Andrei Bulatov<ref>{{Cite book |last1=Bulatov |first1=Andrei |title=Proceedings of the 58th IEEE Annual Symposium on Foundations of Computer Science, FOCS 2017 |publisher=IEEE Computer Society |year=2017 |pages=319–330 |contribution=A Dichotomy Theorem for Nonuniform CSPs |doi=10.1109/FOCS.2017.37|arxiv=1703.03021 |isbn=978-1-5386-3464-6 }}</ref> and Dmitriy Zhuk in 2017.<ref>{{Cite journal |last1=Zhuk |first1=Dmitriy |year=2020 |title=A Proof of the CSP Dichotomy Conjecture |journal=Journal of the ACM |volume=67 |pages=1–78 |arxiv=1704.01914 |doi=10.1145/3402029 |number=5}}</ref>

Other classes for which a complexity dichotomy has been confirmed are

* all [[First-order logic|first-order]] [[Reduct|reducts]] of <math>(\mathbb{Q},<)</math>,<ref>{{Cite journal |last1=Bodirsky |first1=Manuel |last2=Kára |first2=Jan |date=2010-02-08 |title=The complexity of temporal constraint satisfaction problems |url=https://doi.org/10.1145/1667053.1667058 |journal=J. ACM |volume=57 |issue=2 |pages=9:1–9:41 |doi=10.1145/1667053.1667058 |issn=0004-5411|url-access=subscription }}</ref>

* all first-order reducts of the [[Rado graph|countable random graph]],<ref>{{Cite book |last1=Bodirsky |first1=Manuel |title=Proceedings of the 43rd Annual Symposium on Theory of Computing (STOC '11) |title-link=Symposium on Theory of Computing |last2=Pinsker |first2=Michael |publisher=[[Association for Computing Machinery]] |year=2011 |isbn=978-1-4503-0691-1 |pages=655–664 |contribution=Schaefer's theorem for graphs |doi=10.1145/1993636.1993724 |arxiv=1011.2894 |s2cid=47097319}}</ref>

* all first-order reducts of the [[model companion]] of the class of all C-relations,<ref>{{Cite journal |last1=Bodirsky |first1=Manuel |last2=Jonsson |first2=Peter |last3=Pham |first3=Trung Van |date=2017-08-02 |title=The Complexity of Phylogeny Constraint Satisfaction Problems |url=https://doi.org/10.1145/3105907 |journal=ACM Trans. Comput. Logic |volume=18 |issue=3 |pages=23:1–23:42 |doi=10.1145/3105907 |arxiv=1503.07310 |issn=1529-3785}}</ref>

* all first-order reducts of the universal homogenous [[Partially ordered set|poset]],<ref>{{Cite book |last1=Kompatscher |first1=Michael |last2=Pham |first2=Trung Van |date=2017 |chapter= A Complexity Dichotomy for Poset Constraint Satisfaction|title=34th Symposium on Theoretical Aspects of Computer Science (STACS 2017) |series=Leibniz International Proceedings in Informatics |volume=66 |pages=47:1–47:12 |language=en |publisher=Schloss Dagstuhl – Leibniz-Zentrum für Informatik |doi=10.4230/LIPIcs.STACS.2017.47|doi-access=free |isbn=978-3-95977-028-6 }}</ref>

* all first-order reducts of homogenous undirected graphs,<ref>{{Cite journal |last1=Bodirsky |first1=Manuel |last2=Martin |first2=Barnaby |last3=Pinsker |first3=Michael |last4=Pongrácz |first4=András |date=January 2019 |title=Constraint Satisfaction Problems for Reducts of Homogeneous Graphs |url=https://epubs.siam.org/doi/10.1137/16M1082974 |journal=SIAM Journal on Computing |language=en |volume=48 |issue=4 |pages=1224–1264 |doi=10.1137/16M1082974 |issn=0097-5397|arxiv=1602.05819 }}</ref>

* all first-order reducts of all unary structures,<ref>{{Citation |last1=Bodirsky |first1=Manuel |title=A Dichotomy for First-Order Reducts of Unary Structures |date=2018-05-20 |doi=10.23638/LMCS-14(2:13)2018 |last2=Mottet |first2=Antoine|journal=Logical Methods in Computer Science |volume=14 |issue=2 |arxiv=1601.04520 }}</ref>

* all CSPs in the complexity class MMSNP.<ref>{{Cite book |last1=Bodirsky |first1=Manuel |last2=Madelaine |first2=Florent |last3=Mottet |first3=Antoine |chapter=A universal-algebraic proof of the complexity dichotomy for Monotone Monadic SNP |date=2018-07-09 |title=Proceedings of the 33rd Annual ACM/IEEE Symposium on Logic in Computer Science |chapter-url=https://doi.org/10.1145/3209108.3209156 |series=LICS '18 |___location=New York, NY, USA |publisher=Association for Computing Machinery |pages=105–114 |doi=10.1145/3209108.3209156 |arxiv=1802.03255 |isbn=978-1-4503-5583-4}}</ref>

Most classes of CSPs that are known to be tractable are those where the [[hypergraph]] of constraints has bounded [[treewidth]],<ref>{{Cite journal |last1=Barto |first1=Libor |last2=Kozik |first2=Marcin |date=2014-01-01 |title=Constraint Satisfaction Problems Solvable by Local Consistency Methods |url=https://doi.org/10.1145/2556646 |journal=J. ACM |volume=61 |issue=1 |pages=3:1–3:19 |doi=10.1145/2556646 |issn=0004-5411}}</ref> or where the constraints have arbitrary form but there exist equationally non-trivial polymorphisms of the set of constraint relations.<ref>{{Cite book |last=Bodirsky |first=Manuel |url=https://www.cambridge.org/core/books/complexity-of-infinitedomain-constraint-satisfaction/8E6E86C8F8C5C534440266EFB9E584D3 |title=Complexity of Infinite-Domain Constraint Satisfaction |date=2021 |publisher=Cambridge University Press |isbn=978-1-107-04284-1 |series=Lecture Notes in Logic |___location=Cambridge}}</ref>

An ''infinite-___domain dichotomy conjecture''<ref>{{Cite journal |last1=Bodirsky |first1=Manuel |last2=Pinsker |first2=Michael |last3=Pongrácz |first3=András |date=March 2021 |title=Projective Clone Homomorphisms |url=https://www.cambridge.org/core/journals/journal-of-symbolic-logic/article/abs/projective-clone-homomorphisms/3654D0B62D3C45DF6DBD93DDC57B8B02 |journal=The Journal of Symbolic Logic |language=en |volume=86 |issue=1 |pages=148–161 |doi=10.1017/jsl.2019.23 |issn=0022-4812|arxiv=1409.4601 |hdl=2437/268560 }}</ref> has been formulated for all CSPs of reducts of finitely bounded homogenous structures, stating that the CSP of such a structure is in P if and only if its [[Clone (algebra)|polymorphism clone]] is equationally non-trivial, and NP-hard otherwise.

The complexity of such infinite-___domain CSPs as well as of other generalisations (Valued CSPs, Quantified CSPs, Promise CSPs) is still an area of active research.<ref>{{cite arXiv |last=Pinsker |first=Michael |title=Current Challenges in Infinite-Domain Constraint Satisfaction: Dilemmas of the Infinite Sheep |date=2022-03-31 |class=cs.LO |eprint=2203.17182}}</ref>[https://tu-dresden.de/tu-dresden/newsportal/news/erc-synergy-grant-fuer-pococop-komplexitaet-von-berechnungen?set_language=en][https://www.tuwien.at/tu-wien/aktuelles/news/erc-synergy-grant-die-komplexitaet-von-berechnungen]

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>

Line 102 ⟶ 119:

==Further reading==

*[https://www.youtube.com/watch?v=wrs6Lvo5LZM A quick introduction to constraint satisfaction on YouTube]

*Manuel Bodirsky (2021). ''Complexity of Infinite-Domain Constraint Satisfaction''. Cambridge University Press. https://doi.org/10.1017/9781107337534

*{{cite journal|author1=Steven Minton|author2=Andy Philips|author3=Mark D. Johnston|author4=Philip Laird|title=Minimizing Conflicts: A Heuristic Repair Method for Constraint-Satisfaction and Scheduling Problems|journal=Journal of Artificial Intelligence Research|year=1993|volume=58|issue=1–3|pages=161&ndash;205|doi=10.1016/0004-3702(92)90007-k|citeseerx=10.1.1.308.6637|s2cid=14830518 }}

*{{cite book

Line 149 ⟶ 167:

{{DEFAULTSORT:Constraint Satisfaction Problem}}

[[Category:Constraint programming]]

[[Category:NP-complete problems]]