Constraint programming: Difference between revisions

Revision as of 00:52, 1 February 2024

Latest revision as of 10:26, 27 May 2025

(12 intermediate revisions by 10 users not shown)

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

* [[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 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}}

{{Programming paradigms navbox}}

Line 165:

[[Category:Programming paradigms]]

[[Category:Declarative programming]]

<!-- Hidden categories below -->

[[Category:Articles with example code]]