Content deleted Content added
HarsilSPatel (talk | contribs) update the license for the MiniZinc language to the one mentioned on the official website |
GreenC bot (talk | contribs) Reformat 1 archive link. Wayback Medic 2.5 per WP:URLREQ#citeftp |
||
| (44 intermediate revisions by 35 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}}
'''Constraint programming (CP)'''<ref name=":0">{{Cite book|url=https://books.google.com/books?
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
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
{{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 \
}}
* 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
{{math theorem
|Definition
| An
* <math>\mathcal{X_{\mathcal{A}}} \
* <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.
}}
{{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{ such that } 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
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
* 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
* [[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 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 solving ==
There are three main algorithmic techniques for solving constraint satisfaction problems: backtracking search, local search, and dynamic programming.<ref name=":0" />
=== Backtracking search ===
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
== 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
<
% This code works in both YAP and SWI-Prolog using the environment-supplied
% CLPFD constraint solver library. It may require minor modifications to work
Line 124 ⟶ 122:
:- use_module(library(clpfd)).
sendmore(Digits) :-
Digits = [S,E,N,D,M,O,
Digits ins 0..9, % Associate domains to variables
S #\= 0, % Constraint: S must be different from 0
Line 133 ⟶ 131:
#= 10000*M + 1000*O + 100*N + 10*E + Y,
label(Digits). % Start the search
</syntaxhighlight>
The interpreter creates a variable for each letter in the puzzle. The operator <code>ins</code> is used to specify the domains of these variables, so that they range over the set of values {0,1,2,3, ..., 9}. The constraints <code>S#\=0</code> and <code>M#\=0</code> means that these two variables cannot take the value zero. When the interpreter evaluates these constraints, it reduces the domains of these two variables by removing the value 0 from them. Then, the constraint <code>all_different(Digits)</code> is considered; it does not reduce any ___domain, so it is simply stored. The last constraint specifies that the digits assigned to the letters must be such that "SEND+MORE=MONEY" holds when each letter is replaced by its corresponding digit. From this constraint, the solver infers that M=1. All stored constraints involving variable M are awakened: in this case, [[constraint propagation]] on the <code>all_different</code> constraint removes value 1 from the ___domain of all the remaining variables. Constraint propagation may solve the problem by reducing all domains to a single value, it may prove that the problem has no solution by reducing a ___domain to the empty set, but may also terminate without proving satisfiability or unsatisfiability. The '''label''' literals are used to actually perform search for a solution.
==See also==
* [[Combinatorial optimization]]
* [[Concurrent constraint logic programming]]
* [[Constraint logic programming]]
* [[Heuristic (computer science)|Heuristic algorithms]]
* [[List of constraint programming languages]]
* [[Mathematical optimization]]
* [[Nurse scheduling problem]]
* [[Regular constraint]]
* [[Satisfiability modulo theories]]
* [[Traveling tournament problem]]
Line 241 ⟶ 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/
*{{webarchive |url=https://archive.
*{{webarchive |url=https://archive.
{{Programming
{{Types of programming languages}}
{{Authority control}}
Line 252 ⟶ 165:
[[Category:Programming paradigms]]
[[Category:Declarative programming]]
<!-- Hidden categories below -->
[[Category:Articles with example code]]
| |||