Constraint programming: Difference between revisions

Revision as of 00:32, 19 January 2023

Latest revision as of 10:26, 27 May 2025

(22 intermediate revisions by 19 users not shown)

Line 1:

{{Short description|Programming paradigm wherein relations between variables are stated in the form of constraints}}

{{Original research|date=June 2011}}

{{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 23:

{{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 29:

* <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 35:

* 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 46:

Assignment is the association of a variable to a value from its ___domain. A partial assignment is when a subset of the variables of the problem has been assigned. A total assignment is when all the variables of the problem have been assigned.

{{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{ telsuch quethat } 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

|Property

|Given <math>\mathcal{A} = (\mathcal{X_{\mathcal{A}}}, \mathcal{V_{\mathcal{A}}})</math> an assignation (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 \subset \mathcal{X_{\mathcal{A}}}</math>, the assignation <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:

Line 59 ⟶ 57:

* finding a solution (satisfying all the constraints);

* finding all the solutions of the problem;

* [[automated theorem proving|proving]] the unsatisfiability of the problem.

== Constraint optimization problem ==

Line 67 ⟶ 65:

An ''optimal solution'' to a minimization (maximization) COP is a solution that minimizes (maximizes) the value of the ''objective function''.

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

* finding a solution (satisfying all the constraints);

Line 79 ⟶ 77:

* Refinement model: variables in the problem are initially unassigned, and each variable is assumed to be able to contain any value included in its range or ___domain. As computation progresses, values in the ___domain of a variable are pruned if they are shown to be incompatible with the possible values of other variables, until a single value is found for each variable.

* Perturbation model: variables in the problem are assigned a single initial value. At different times one or more variables receive perturbations (changes to their old value), and the system propagates the change trying to assign new values to other variables that are consistent with the perturbation.

[[Constraint propagation]] in [[Constraint Satisfaction Problems|constraint satisfaction problems]] is a typical example of a refinement model, and formula evaluation in [[spreadsheet]]s are a typical example of a perturbation model.

The refinement model is more general, as it does not restrict variables to have a single value, it can lead to several solutions to the same problem. However, the perturbation model is more intuitive for programmers using mixed imperative constraint object-oriented languages.<ref>Lopez, G., Freeman-Benson, B., & Borning, A. (1994, January). [ftp://trout.cs.washington.edu/tr/1993/09/UW-CSE-93-09-04.pdf Kaleidoscope: A constraint imperative programming language.]{{dead link|date=May 2025|bot=medic}}{{cbignore|bot=medic}} In ''Constraint Programming'' (pp. 313-329). Springer Berlin Heidelberg.</ref>

==Domains==

The constraints used in constraint programming are typically over some specific domains. Some popular domains for constraint programming are:

* [[Boolean datatypedata type|booleanBoolean]] domains, where only true/false constraints apply ([[Boolean satisfiability problem|SAT problem]])

* [[integer]] domains, [[Rational numbers|rational]] domains

* [[Interval_(mathematics)|interval]] domains, in particular for [[Automated planning and scheduling|scheduling]] problems<ref>{{Cite book |last1=Baptiste |first1=Philippe |author-link1=Philippe Baptiste|url=https://books.google.com/books?id=qUzhBwAAQBAJ |title=Constraint-Based Scheduling: Applying Constraint Programming to Scheduling Problems |last2=Pape |first2=Claude Le |last3=Nuijten |first3=Wim |date=2012-12-06 |publisher=Springer Science & Business Media |isbn=978-1-4615-1479-4 |language=en}}</ref>

* [[Interval_(mathematics)|interval]] domains, in particular for scheduling problems

* [[Linear algebra|linear]] domains, where only [[linear]] functions are described and analyzed (although approaches to [[non-linear]] problems do exist)

* [[wiktionary:finite|finite]] domains, where constraints are defined over [[finite set]]s

Line 99 ⟶ 97:

'''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|citeseerx=10.1.1.398.4070}}</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 ==

Line 114 ⟶ 112:

=== Dynamic programming ===

{{Main|Dynamic programming}}

'''Dynamic programming''' is both a [[mathematical optimization]] method and a computer programming method. It refers to simplifying a complicated problem by breaking it down into simpler sub-problems in a [[Recursion|recursive]] manner. While some [[decision problemsproblem]]s cannot be taken apart this way, decisions that span several points in time do often break apart recursively. Likewise, in computer science, if a problem can be solved optimally by breaking it into sub-problems and then recursively finding the optimal solutions to the sub-problems, then it is said to have [[optimal substructure]].

== Example ==

The syntax for expressing constraints over finite domains depends on the host language. The following is a [[Prolog]] program that solves the classical [[alphametic]] puzzle [[Verbal arithmetic|SEND+MORE=MONEY]] in constraint logic programming:

<syntaxhighlight lang="prolog">

% This code works in both YAP and SWI-Prolog using the environment-supplied

Line 139 ⟶ 137:

==See also==

* [[Combinatorial optimization]]

* [[Constraint logic programming]]

* [[Concurrent constraint logic programming]]

* [[Constraint logic programming]]

* [[Mathematical optimization]]

* [[Heuristic (computer science)|Heuristic algorithms]]

* [[List of constraint programming languages]]

* [[Mathematical optimization]]

* [[Nurse scheduling problem]]

* [[Regular constraint]]

* [[Satisfiability modulo theories]]

* [[Traveling tournament problem]]

Line 154:

*[http://www.a4cp.org/ Association for Constraint Programming]

*[http://www.a4cp.org/events/cp-conference-series CP Conference Series]

*[http://kti.ms.mff.cuni.cz/~bartak/constraints/index.html Guide to Constraint Programming]

*{{webarchive |url=https://archive.today/20121205051244/http://www.mozart-oz.org/ |date=December 5, 2012 |title=The Mozart Programming System}}, an [[Oz (programming language)|Oz]]-based free software ([[X11X Window System]]- style)

*{{webarchive |url=https://archive.today/20130107222548/http://4c.ucc.ie/web/index.jsp |date=January 7, 2013 |title= Cork Constraint Computation Centre}}

*[https://sofdem.github.io/gccat/index.html Global Constraint Catalog]

{{Programming paradigms navbox}}

{{Types of programming languages}}

{{Authority control}}

Line 165:

[[Category:Programming paradigms]]

[[Category:Declarative programming]]

<!-- Hidden categories below -->

[[Category:Articles with example code]]