Constraint programming: Difference between revisions

Revision as of 14:01, 28 January 2025

Latest revision as of 10:26, 27 May 2025

(3 intermediate revisions by 3 users not shown)

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

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