Constraint programming: Difference between revisions

Revision as of 01:01, 20 September 2023

Revision as of 00:05, 15 October 2023

Line 3:

{{Programming paradigms}}

'''Constraint programming (CP)'''<ref name=":0">{{Cite book|url=https://books.google.com/books?id=Kjap9ZWcKOoC&q=handbook+of+constraint+programming&pg=PP1|title=Handbook of Constraint Programming|last1=Rossi|first1=Francesca|author1link = Francesca Rossi|last2=Beek|first2=Peter van|last3=Walsh|first3=Toby|author3link = Toby Walsh|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 addition 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-SIGACT symposiumSymposium on Principles of programmingProgramming languagesLanguages]]. 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]].

Instead of logic programming, constraints can be mixed with [[functional programming]], [[term rewriting]], and [[imperative language]]s.

Line 24:

{{main|Constraint satisfaction problem}}

A constraint is a relation between multiple variables whichthat limits the values these variables can take simultaneously.

{{math theorem

|Definition

Line 30:

* <math>\mathcal{X} = \{x_1, \dots, x_n \}</math> is the set of variables of the problem;

* <math>\mathcal{D} = \{\mathcal{D}_1, \dots, \mathcal{D}_n \}</math> is the set of domains of the variables, i.e., for all <math>k \in [1; n]</math> we have <math>x_k \in \mathcal{D}_k</math>;

* <math>\mathcal{C} = \{C_1, \dots, C_m \}</math> is a set of constraints. A constraint <math>C_i=(\mathcal{X}_i, \mathcal{R}_i)</math> is defined by a set <math>\mathcal{X}_i = \{x_{i_1}, \dots, x_{i_k}\}</math> of variables and a relation <math>\mathcal{R}_i \subsetsubseteq \mathcal{D}_{i_1} \times \dots \times \mathcal{D}_{i_k}</math> whichthat defines the set of values allowed simultaneously for the variables of <math>\mathcal{X}_i</math>:.

}}

Line 36:

* extensional constraints: constraints are defined by enumerating the set of values that would satisfy them;

* arithmetic constraints: constraints are defined by an arithmetic expression, i.e., using <math><, >, \leq, \geq, =, \neq,...</math>;

* logical constraints: constraints are defined with an explicit semanticsemantics, i.e., ''AllDifferent'', ''AtMost'',''...''

{{math theorem

|Definition

| An assignment (or model) <math>\mathcal{A}</math> of a CSP <math>P = (\mathcal{X},\mathcal{D},\mathcal{C})</math> is defined by the couple <math>\mathcal{A} = (\mathcal{X_{\mathcal{A}}}, \mathcal{V_{\mathcal{A}}})</math> where:

* <math>\mathcal{X_{\mathcal{A}}} \subsetsubseteq \mathcal{X} </math> is a subset of variable;

* <math>\mathcal{V_{\mathcal{A}}} = \{ v_{\mathcal{A}_1}, \dots, v_{\mathcal{A}_k}\} \in \{ \mathcal{D}_{\mathcal{A}_1}, \dots, \mathcal{D}_{\mathcal{A}_k}\}</math> is the tuple of the values taken by the assigned variables.

}}

Line 49:

{{math theorem

|Property

|Given <math>\mathcal{A} = (\mathcal{X_{\mathcal{A}}}, \mathcal{V_{\mathcal{A}}})</math> an assignationassignment (partial or total) of a CSP <math>P = (\mathcal{X},\mathcal{D},\mathcal{C})</math>, and <math>C_i = (\mathcal{X}_i, \mathcal{R}_i)</math> a constraint of <math>P</math> such as <math>\mathcal{X}_i \subsetsubseteq \mathcal{X_{\mathcal{A}}}</math>, the assignationassignment <math>\mathcal{A}</math> satisfies the constraint <math>C_i</math> if and only if all the values <math>\mathcal{V}_{\mathcal{A}_i} = \{ v_i \in \mathcal{V}_{\mathcal{A}} \mbox{ tel que } x_i \in \mathcal{X}_{i} \}</math> of the variables of the constraint <math>C_i</math> belongs to <math>\mathcal{R}_i</math>.

}}

{{math theorem

|Definition

|A solution of a CSP is a total assignationassignment whichthat satisfiedsatisfies all the constraints of the problem.}}

During the search of the solutions of a CSP, a user can wish for: