Constraint (mathematics): Difference between revisions

Revision as of 14:55, 15 May 2022

Revision as of 21:51, 22 September 2022

Line 33:

== Global constraints ==

Global constraints<ref>{{Cite book|title=Handbook of constraint programming|last1=Rossi|first1=Francesca|last2=Van Beek|first2=Peter|last3=Walsh|first3=Toby|date=2006|publisher=Elsevier|isbn=9780080463643|edition=1st|___location=Amsterdam|chapter=7|oclc=162587579}}</ref> are constraints representing a specific relation on a number of variables, taken altogether. Some of them, such as the [https://sofdem.github.io/gccat/gccat/Calldifferent.html <code>alldifferent</code>] constraint, can be rewritten as a conjunction of atomic constraints in a simpler language: the <code>alldifferent</code> constraint holds on ''n'' variables <math>x_1... x_n</math>, and is satisfied iffif the variables take values which are pairwise different. It is semantically equivalent to the conjunction of inequalities <math>x_1 \neq x_2, x_1 \neq x_3..., x_2 \neq x_3, x_2 \neq x_4 ... x_{n-1} \neq x_n</math>. Other global constraints extend the expressivity of the constraint framework. In this case, they usually capture a typical structure of combinatorial problems. For instance, the <code>[[Regular constraint|regular]]</code> constraint expresses that a sequence of variables is accepted by a [[deterministic finite automaton]].

Global constraints are used<ref>{{Cite book|title=Principles and Practice of Constraint Programming CP 2003 00 : 9th International Conference, CP 2003, Kinsale, Ireland, September 29 October 3, 2003. Proceedings|date=2003|publisher=Springer-Verlag Berlin Heidelberg|last=Rossi|first=Francesca|isbn=9783540451938|___location=Berlin|oclc=771185146}}</ref> to simplify the modeling of [[constraint satisfaction problems]], to extend the expressivity of constraint languages, and also to improve the [[Constraint programming|constraint resolution]]: indeed, by considering the variables altogether, infeasible situations can be seen earlier in the solving process. Many of the global constraints are referenced into an [https://sofdem.github.io/gccat/ online catalog.]