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: 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.
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).
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.
In this basic backtracking algorithm, consistency is defined as the satisfaction of all constraints whose variables are all assigned.
Backjumping allows saving part of the search by backtracking "more than one variable" in some cases.
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.
The most popular constraint propagation method is the AC-3 algorithm, which enforces arc consistency.
In practice, local search appears to work well when these changes are also affected by random choices.
[15] Since every computational decision problem is polynomial-time equivalent to a CSP with an infinite template,[16] 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.
These CSPs thus provide one of the largest known subsets of NP which avoids NP-intermediate problems.
This finite-domain dichotomy conjecture was first formulated by Tomás Feder and Moshe Vardi,[17] and finally proven independently by Andrei Bulatov[18] and Dmitriy Zhuk in 2017.
[28] An infinite-domain dichotomy conjecture[29] 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.
Each problem takes a Boolean formula as input and the task is to compute the number of satisfying assignments.
This rigid model is a shortcoming that makes it difficult to represent problems easily.
[33] Several modifications of the basic CSP definition have been proposed to adapt the model to a wide variety of problems.
Dynamic CSPs[34] (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.
[35] 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).
The solving method can be classified according to the way in which information is transferred: 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).
Some types of flexible CSPs include: In DCSPs[36] each constraint variable is thought of as having a separate geographic location.