Constraint programming: Difference between revisions

Revision as of 14:05, 8 March 2020

Revision as of 05:20, 5 April 2020

Line 99:

'''Local consistency''' conditions are properties of [[Constraint satisfaction problem|constraint satisfaction problems]] related to the [[consistency]] of subsets of variables or constraints. They can be used to reduce the search space and make the problem easier to solve. Various kinds of local consistency conditions are leveraged, including '''node consistency''', '''arc consistency''', and '''path consistency'''.

Every local consistency condition can be enforced by a transformation that changes the problem without changing its solutions. Such a transformation is called '''[[constraint propagation]]'''.<ref>{{Citation|last=Bessiere|first=Christian|chapter=Constraint Propagation|date=2006|pages=29–83|publisher=Elsevier|isbn=9780444527264|doi=10.1016/s1574-6526(06)80007-6|title=Handbook of Constraint Programming|volume=2|series=Foundations of Artificial Intelligence}}</ref>. Constraint propagation works by reducing domains of variables, strengthening constraints, or creating new ones. This leads to a reduction of the search space, making the problem easier to solve by some algorithms. Constraint propagation can also be used as an unsatisfiability checker, incomplete in general but complete in some particular cases.

== Constraint solving ==