Editing Constraint satisfaction problem (section)

==Variants==
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.<ref>{{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
 }}
</ref> Several modifications of the basic CSP definition have been proposed to adapt the model to a wide variety of problems.

===Dynamic CSPs===
'''Dynamic CSPs'''<ref>Dechter, 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.</ref> (''DCSP''s) 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.<ref>[http://www.aaai.org/Papers/AAAI/1994/AAAI94-302.pdf Solution reuse in dynamic constraint satisfaction problems], Thomas Schiex</ref> 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:
* [[Oracle machine|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 (optimization)|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 CSP'''s 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 constraint satisfaction problem|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 logic|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<ref name="cfl">
{{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
 }}</ref> 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.