Constraint programming: Difference between revisions

Revision as of 07:23, 1 December 2019

Revision as of 16:32, 26 January 2020

Line 2:

{{Programming paradigms}}

'''Constraint programming (CP)'''<ref name=":0">{{Cite book|url=https://books.google.com/?id=Kjap9ZWcKOoC&pg=PP1&dq=handbook+of+constraint+programming|title=Handbook of Constraint Programming|last=Rossi|first=Francesca|last2=Beek|first2=Peter van|last3=Walsh|first3=Toby|date=2006-08-18|publisher=Elsevier|isbn=9780080463803|language=en}}</ref> is a paradigm for solving combinatorial problems that draws on a wide range of techniques from artificial intelligence, [[computer science]], and [[operations research]]. In constraint programming, users declaratively state the [[Constraint (mathematics)|constraints]] on the feasible solutions for a set of decision variables. Constraints differ from the common [[Language primitive|primitives]] of [[imperative programming]] languages in that they do not specify a step or sequence of steps to execute, but rather the properties of a solution to be found. In additions to constraints, users also need to specify a method to solve these constraints. This typically draws upon standard methods like chronological [[backtracking]] and [[constraint propagation]], but may use customized code like a problem specific branching [[Heuristic (computer science)|heuristic]].

Constraint programming takes its root from and can be expressed in the form of [[constraint logic programming]], which embeds constraints into a [[logic program]]. This variant of logic programming is due to Jaffar and Lassez,<ref>Jaffar, Joxan, and J-L. Lassez. "[https://dl.acm.org/citation.cfm?id=41635 Constraint logic programming]." Proceedings of the 14th ACM SIGACT-SIGPLAN symposium on Principles of programming languages. ACM, 1987.</ref> who extended in 1987 a specific class of constraints that were introduced in [[Prolog II]]. The first implementations of constraint logic programming were [[Prolog III]], [[CLP(R)]], and [[CHIP (programming language)|CHIP]].

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|'''[[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 ==