Constraint programming: Difference between revisions

Revision as of 03:07, 24 July 2024

Latest revision as of 10:26, 27 May 2025

(10 intermediate revisions by 9 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 81 ⟶ 79:

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

Line 88 ⟶ 86:

* [[Boolean data type|Boolean]] 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]]