Constraint satisfaction problem

Formally, a constraint satisfaction problem is defined as a triple ${\displaystyle \langle X,D,C\rangle }$, where [13]

• ${\displaystyle X=\{X_{1},\ldots ,X_{n}\}}$ is a set of variables,
• ${\displaystyle D=\{D_{1},\ldots ,D_{n}\}}$ is a set of their respective domains of values, and
• ${\displaystyle C=\{C_{1},\ldots ,C_{m}\}}$ is a set of constraints.

Each variable ${\displaystyle X_{i}}$ can take on the values in the nonempty domain ${\displaystyle D_{i}}$. Every constraint ${\displaystyle C_{j}\in C}$ is in turn a pair ${\displaystyle \langle t_{j},R_{j}\rangle }$, where ${\displaystyle t_{j}\subseteq X}$ is a subset of ${\displaystyle k}$ variables and ${\displaystyle R_{j}}$ is a ${\displaystyle k}$-ary relation on the corresponding subset of domains ${\displaystyle D_{j}}$. 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 ${\displaystyle v}$ satisfies a constraint ${\displaystyle \langle t_{j},R_{j}\rangle }$ if the values assigned to the variables ${\displaystyle t_{j}}$ satisfy the relation ${\displaystyle 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.[14]

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.

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.[18] Several modifications of the basic CSP definition have been proposed to adapt the model to a wide variety of problems.

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

• A quick introduction to constraint satisfaction on YouTube
• Steven Minton; Andy Philips; Mark D. Johnston; Philip Laird (1993). "Minimizing Conflicts: A Heuristic Repair Method for Constraint-Satisfaction and Scheduling Problems". Journal of Artificial Intelligence Research. 58 (1–3): 161–205. CiteSeerX 10.1.1.308.6637. doi:10.1016/0004-3702(92)90007-k. S2CID 14830518.
• Tsang, Edward (1993). Foundations of Constraint Satisfaction. Academic Press. ISBN 0-12-701610-4
• Chen, Hubie (December 2009). "A Rendezvous of Logic, Complexity, and Algebra". ACM Computing Surveys. 42 (1): 1–32. arXiv:cs/0611018. doi:10.1145/1592451.1592453. S2CID 11975818.
• Dechter, Rina (2003). Constraint processing. Morgan Kaufmann. ISBN 1-55860-890-7
• Apt, Krzysztof (2003). Principles of constraint programming. Cambridge University Press. ISBN 9780521825832. ISBN 0-521-82583-0
• Lecoutre, Christophe (2009). Constraint Networks: Techniques and Algorithms. ISTE/Wiley. ISBN 978-1-84821-106-3
• Tomás Feder, Constraint satisfaction: a personal perspective, manuscript.
• Constraints archive
• Forced Satisfiable CSP Benchmarks of Model RB Archived 2021-01-25 at the Wayback Machine
• Benchmarks – XML representation of CSP instances
• XCSP3 – An XML-based format designed to represent CSP instances
• Constraint Propagation – Dissertation by Guido Tack giving a good survey of theory and implementation issues