Constraint programming: Difference between revisions

Revision as of 08:15, 11 January 2024

Latest revision as of 10:26, 27 May 2025

(13 intermediate revisions by 11 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]].

Line 47 ⟶ 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 assignment (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 \subseteq \mathcal{X_{\mathcal{A}}}</math>, the assignment <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 assignment (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 \subseteq \mathcal{X_{\mathcal{A}}}</math>, the assignment <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>.

}}

Line 80 ⟶ 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>

* [[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 115 ⟶ 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 140 ⟶ 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 155 ⟶ 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}}

{{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]]