Constraint programming
|
|
Constraint programming is a programming paradigm in which a set of constraints that a solution must meet are specified rather than set of steps to obtain such a solution.
Constraint programming is related to logic programming and, since both are Turing-complete, any logic program can be translated into an equivalent constraint program and vice versa. This is sometimes useful in practice, since a constraint solving program may find an answer faster than a logic derivation program, and it might be desirable to perform this translation before executing a logic program.
The difference between the two is largely in their styles and approaches to modeling the world. Some problems are more natural (and thus, simpler) to write as logic programs, while some are more natural to write as constraint programs.
The constraint programming approach is to search for a state of the world in which a large number of constraints are satisfied at the same time. A problem is typically stated as a state of the world containing a number of unknown variables. The constraint program searches for values for all the variables.
Temporal concurrent constraint programming (TCC) and non-deterministic temporal concurrent constraint programming (NTCC) are variants of constraint programming that can deal with time.
Some popular application domains for constraint programming are:
- boolean domains, where only true/false constraints apply
- Integer domains, rational domains
- linear domains, where only linear functions are described and analyzed (although approaches to non-linear problems do exist)
- finite domains, where constraints are defined over countable sets
- Mixed domains, involving two or more of the abovede:Constraintprogrammierung