Constraint satisfaction problem

Kakqqk

Not to be confused with Communicating sequential processes.

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.

Flexible CSPs

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.

Decentralized CSPs

In DCSPs 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.

See also

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

Further reading

• 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