Added to Favorites

Related Searches

Definitions

Constraint programming is a programming paradigm where relations between variables are stated in the form of constraints. Constraints differ from the common primitives of other programming languages in that they do not specify a step or sequence of steps to execute, but rather the properties of a solution to be found. This makes Constraint Programming a form of declarative programming. The constraints used in constraint programming are of various kinds: those used in constraint satisfaction problems (e.g. "A or B is true"), those solved by the simplex algorithm (e.g. "x < 5")), and others. Constraints are usually embedded within a programming language or provided via separate software libraries.## Constraint logic programming

## Domains

## Concurrent Constraint Programming

## Imperative constraint programming

## See also

## External links

Constraint programming began with constraint logic programming, which embeds constraints into a logic program. This variant of logic programming is due to Jaffar and Lassez, who extended in 1987 a specific class of constraints that were introduced in Prolog II. The first implementations of constraint logic programming were Prolog III, CLP(R), and CHIP. Several constraint logic programming interpreters exist today, for example GNU Prolog.

Other than logic programming, constraints can be mixed with functional programming, term rewriting, and imperative languages. Programming languages with built-in support for constraints include Oz (functional programming) and Kaleidoscope (imperative programming). Mostly, constraints are implemented in imperative languages via constraint solving toolkits, which are separate libraries for an existing imperative language.

Constraint programming is an embedding of constraints in a host language. The first host languages used were logic programming languages, so the field was initially called constraint logic programming. The two paradigms share many important features, like logical variables and backtracking. Today most Prolog implementations include one or more libraries for constraint logic programming.

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 constraint logic languages are:

- B-Prolog (Prolog based, proprietary)
- CHIP V5 (Prolog based, also includes C++ and C libraries, proprietary)
- Ciao Prolog (Prolog based, Free software: GPL/LGPL)
- ECLiPSe (Prolog based, open source)
- SICStus (Prolog based, proprietary)
- GNU Prolog
- YAP Prolog
- SWI Prolog a free Prolog system containing several libraries for constraint solving
- Claire

The constraints used in constraint programming are typically over some specific domains. Some popular domains for constraint programming are:

- boolean domains, where only true/false constraints apply (SAT problem)
- 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 finite sets
- mixed domains, involving two or more of the above

Finite domains is one of the most successful domains of constraint programming. In some areas (like operations research) constraint programming is often identified with constraint programming over finite domains.

Finite domain solvers are useful for solving constraint satisfaction problems, and are often based on arc consistency or one of its approximations.

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 SEND+MORE=MONEY in constraint logic programming:

sendmore(Digits) :-

Digits = [S,E,N,D,M,O,R,Y], % Create variables

` Digits :: [0..9], % Associate domains to variables`

` S #= 0, % Constraint: S must be different from 0`

` M #= 0,`

` alldifferent(Digits), % all the elements must take different values`

1000*S + 100*E + 10*N + D % Other constraints

+ 1000*M + 100*O + 10*R + E

` #= 10000*M + 1000*O + 100*N + 10*E + Y,`

` labeling(Digits). % Start the search`

The interpreter creates a variable for each letter in the puzzle. The symbol `::`

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 S#=0 and M#=0 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 alldifferent(Digits) 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 `alldifferent`

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 labeling literals are used to actually perform search for a solution.

Some popular concurrent constraint programming languages are:

For information on concurrent constraint variables which are the basis of concurrent constraint programming, see Future (programming).

Constraint programming is often realized in imperative programming via a separate library. Some popular libraries for constraint programming are:

- Choco (Java library, free software: X11 style)
- Comet (C style language for constraint programming, free binaries available for non-commercial use)
- Disolver (C++ library, proprietary)
- Gecode (C++ library, free software: X11 style)
- Gecode/J (Java binding to Gecode, free software: X11 style)
- ILOG CP Optimizer (C++, Java, .NET libraries, proprietary)
- ILOG CP (C++ library, proprietary)
- JaCoP (Java library, proprietary)
- JOpt (Java library, free software)
- Koalog Constraint Solver (Java library, proprietary)
- Minion (C++ program, GPL)
- python-constraint (Python library, GPL)

- Combinatorial optimization
- Constraint satisfaction
- Constraint logic programming
- Heuristic algorithms
- Mathematical programming (Optimization theory)

- Information on the annual CP conference
- On-Line Guide to Constraint Programming
- Program Does Not Equal Program: Constraint Programming and its Relationship to Mathematical Programming
- Mozart (Oz based, Free software: X11 style)
- Cork Constraint Computation Centre (4C)

Wikipedia, the free encyclopedia © 2001-2006 Wikipedia contributors (Disclaimer)

This article is licensed under the GNU Free Documentation License.

Last updated on Friday October 03, 2008 at 09:01:59 PDT (GMT -0700)

View this article at Wikipedia.org - Edit this article at Wikipedia.org - Donate to the Wikimedia Foundation

This article is licensed under the GNU Free Documentation License.

Last updated on Friday October 03, 2008 at 09:01:59 PDT (GMT -0700)

View this article at Wikipedia.org - Edit this article at Wikipedia.org - Donate to the Wikimedia Foundation

Copyright © 2014 Dictionary.com, LLC. All rights reserved.