constraint satisfaction problem

Formally, a constraint satisfaction problem is defined as a triple $\backslash langle\; X,D,C\; \backslash rangle$, where{{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}}

• $X\; =\; \backslash \{X\_1,\; \backslash ldots,X\_n\backslash \}$ is a set of variables,
• $D\; =\; \backslash \{D\_1,\; \backslash ldots,\; D\_n\backslash \}$ is a set of their respective domains of values, and
• $C\; =\; \backslash \{C\_1,\; \backslash ldots,\; C\_m\backslash \}$ is a set of constraints.

Each variable $X\_i$ can take on the values in the nonempty domain $D\_i$.

Every constraint $C\_j\; \backslash in\; C$ is in turn a pair $\backslash langle\; t\_j,R\_j\; \backslash rangle$, where $t\_j\; \backslash subseteq\; \backslash \{1,\; 2,\; \backslash ldots,\; n\backslash \}$ is a set of $k$ indices and $R\_j$ is a $k$-ary relation on the corresponding product of domains $\backslash times\_\{i\; \backslash in\; t\_j\}\; D\_i$ 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 $v$ satisfies a constraint $\backslash langle\; t\_j,\; R\_j\; \backslash rangle$ if the values assigned to the variables $t\_j$ satisfy the relation $R\_j$.

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.

Constraint satisfaction problems on finite domains are typically solved using a form of search. The most used techniques are variants of backtracking, constraint propagation, and local search. These techniques are also often combined, as in the VLNS method, and current research involves other technologies such as linear programming.{{Cite conference|title=Hybrid optimization : the ten years of CPAIOR|date=2011|publisher=Springer|editor1=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}}

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 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 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 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 algorithms.

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

Since every computational decision problem is polynomial-time equivalent to a CSP with an infinite template,{{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}} general CSPs can have arbitrary complexity. In particular, there are also CSPs within the class of NP-intermediate problems, whose existence was demonstrated by Ladner, under the assumption that P ≠ NP.

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 or NP-complete. These CSPs thus provide one of the largest known subsets of NP which avoids NP-intermediate problems. A complexity dichotomy was first proven by Schaefer for Boolean CSPs, i.e. CSPs over a 2-element domain and where all the available relations are Boolean operators. 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,{{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}} and finally proven independently by Andrei Bulatov{{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 }} and Dmitriy Zhuk in 2017.{{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}}

Other classes for which a complexity dichotomy has been confirmed are

• all first-order reducts of ,{{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}}
• all first-order reducts of the countable random graph,{{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}}
• all first-order reducts of the model companion of the class of all C-relations,{{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}}
• all first-order reducts of the universal homogenous poset,{{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 }}
• all first-order reducts of homogenous undirected graphs,{{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 }}
• all first-order reducts of all unary structures,{{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 }}
• all CSPs in the complexity class MMSNP.{{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}}

Most classes of CSPs that are known to be tractable are those where the hypergraph of constraints has bounded treewidth,{{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}} or where the constraints have arbitrary form but there exist equationally non-trivial polymorphisms of the set of constraint relations.{{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}}

An infinite-domain dichotomy conjecture{{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 }} 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 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.{{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}}[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.{{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}}

A similar situation exists between the functional classes FP and #P. By a generalization of Ladner's theorem, there are also problems in neither FP nor #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 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.{{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 = 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}}

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

}}

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

Dynamic CSPsDechter, 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. (DCSPs) 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.[http://www.aaai.org/Papers/AAAI/1994/AAAI94-302.pdf Solution reuse in dynamic constraint satisfaction problems], Thomas Schiex 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:

• 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.
• Constraint recording: new constraints are defined in each stage of the search to represent the learning of inconsistent group of decisions. Those constraints are carried over to the new CSP problems.

Classic CSPs treat constraints as hard, meaning that they are imperative (each solution must satisfy all of them) and inflexible (in the sense that they must be completely satisfied or else they are completely violated). Flexible CSPs relax those assumptions, partially relaxing the constraints and allowing the solution to not comply with all of them. This is similar to preferences in preference-based planning. Some types of flexible CSPs include:

• MAX-CSP, where a number of constraints are allowed to be violated, and the quality of a solution is measured by the number of satisfied constraints.
• Weighted CSP, a MAX-CSP in which each violation of a constraint is weighted according to a predefined preference. Thus satisfying constraint with more weight is preferred.
• Fuzzy CSP model constraints as fuzzy relations in which the satisfaction of a constraint is a continuous function of its variables' values, going from fully satisfied to fully violated.

In DCSPs

{{Citation

| last1 = Duffy | first1 = K.R.

| last2 = Leith | first2 = D.J.

| contribution = Decentralized Constraint Satisfaction

| title = IEEE/ACM Transactions on Networking, 21(4)

| volume = 21

| issue = 4

| pages = 1298–1308

| date = August 2013

| doi = 10.1109/TNET.2012.2222923

| arxiv = 1103.3240

| s2cid = 11504393

}} each constraint variable is thought of as having a separate geographic location. Strong constraints are placed on information exchange between variables, requiring the use of fully distributed algorithms to solve the constraint satisfaction problem.

• Constraint composite graph
• Constraint programming
• Declarative programming
• Constrained optimization (COP)
• Distributed constraint optimization
• Graph homomorphism
• Unique games conjecture
• Weighted constraint satisfaction problem (WCSP)

{{Reflist}}

• [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–205|doi=10.1016/0004-3702(92)90007-k|citeseerx=10.1.1.308.6637|s2cid=14830518 }}
• {{cite book

| first=Edward

| last=Tsang

| title=Foundations of Constraint Satisfaction

| year=1993

| publisher=Academic Press

| url=http://www.bracil.net/edward/FCS.html

}} {{isbn|0-12-701610-4}}

• {{Cite journal | last1 = Chen | first1 = Hubie | date=December 2009 | title = A Rendezvous of Logic, Complexity, and Algebra | journal = ACM Computing Surveys | volume = 42 | issue = 1 | pages = 1–32 |arxiv=cs/0611018 | doi=10.1145/1592451.1592453| s2cid = 11975818 }}
• {{cite book

| first=Rina

| last=Dechter

| title=Constraint processing

| publisher=Morgan Kaufmann

| year=2003

| url=http://www.ics.uci.edu/~dechter/books/index.html

}} {{isbn|1-55860-890-7}}

• {{cite book

| first=Krzysztof

| last=Apt

| author-link=Krzysztof R. Apt

| title=Principles of constraint programming

| url=https://archive.org/details/principlesofcons0000aptk

| url-access=registration

| publisher=Cambridge University Press

| year=2003

| isbn=9780521825832

}} {{isbn|0-521-82583-0}}

• {{cite book

| first=Christophe

| last=Lecoutre

| title=Constraint Networks: Techniques and Algorithms

| publisher=ISTE/Wiley

| year=2009

| url=http://www.iste.co.uk/index.php?f=a&ACTION=View&id=250

}} {{isbn|978-1-84821-106-3}}

• Tomás Feder, [http://theory.stanford.edu/~tomas/consmod.pdf Constraint satisfaction: a personal perspective], manuscript.
• [https://web.archive.org/web/20060213071549/http://4c.ucc.ie/web/archive/index.jsp Constraints archive]
• [http://www.nlsde.buaa.edu.cn/~kexu/benchmarks/benchmarks.htm Forced Satisfiable CSP Benchmarks of Model RB] {{Webarchive|url=https://web.archive.org/web/20210125071920/http://www.nlsde.buaa.edu.cn/~kexu/benchmarks/benchmarks.htm |date=2021-01-25 }}
• [https://web.archive.org/web/20060813201559/http://www.cril.univ-artois.fr/~lecoutre/research/benchmarks/benchmarks.html Benchmarks – XML representation of CSP instances]
• [http://xcsp.org XCSP3 – An XML-based format designed to represent CSP instances]
• [https://web.archive.org/web/20090419182234/http://www.ps.uni-sb.de/Papers/abstracts/tackDiss.html Constraint Propagation] – Dissertation by Guido Tack giving a good survey of theory and implementation issues

{{Industrial and applied mathematics}}

{{DEFAULTSORT:Constraint Satisfaction Problem}}

Category:Constraint programming

Category:NP-complete problems