|
Constraint programming is a programming paradigm where relations between variables can be 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. The constraints used in constraint programming are of various kinds: those used in constraint satisfaction problems, those solved by the simplex algorithm, and others. Constraints are usually embedded within a programming language or provided via separate software libraries. A programming paradigm is a paradigmatic style of programming (compare with a methodology, which is a paradigmatic style of doing software engineering). ...
Constraint-satisfaction problems or CSPs are mathematical problems where one must find states or objects in a system that satisfy a number of constraints or criteria. ...
In mathematical optimization theory, the simplex algorithm, created by the North American mathematician George Dantzig in 1947, is a popular technique for numerical solution of the linear programming problem. ...
In computer science, a library is a collection of subprograms used to develop software. ...
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. Bold textConstraint logic programming is a form of constraint programming, in which logic programming is extended to include concepts from constraint satisfaction. ...
Logic programming (sometimes called logical programming) is programming that makes use of pattern-directed invocation of procedures from assertions and goals. ...
GNU Prolog A Native Prolog Compiler with Constraint Solving over Finite Domains GNU Prolog is a free Prolog compiler with constraint solving over finite domains developed by Daniel Diaz. ...
Other than logic programming, constraints can be mixed with functional programming, term rewriting, and imperative languages. Constraints in functional programming are implemented in the multi-paradigm programming language Oz. Constraints are embedded in an imperative language in Kaleidoscope. However, constraints are implemented in imperative languages mostly via constraint solving toolkits, which are separate libraries for an existing imperative language. ILOG Solver is an example of such a constraint programming library for C++. Functional programming is a programming paradigm that conceives computation as the evaluation of mathematical functions and avoids state and mutable data. ...
Rewriting in mathematics, computer science and logic covers a wide range of methods of transforming strings, written in some fixed alphabet, that are not deterministic but are governed by explicit rules. ...
In computer science, imperative programming, as opposed to declarative programming, is a programming paradigm that describes computation in terms of a program state and statements that change the program state. ...
A multiparadigm programming language is a programming language that supports more than one programming paradigm. ...
Oz is a multi-paradigm programming language. ...
The Kaleidoscope programming language is a constraint programming language embedding constraints into an imperative object-oriented language. ...
In computer science, a library is a collection of subprograms used to develop software. ...
C++ (IPA pronounciation: ) is a general-purpose, high-level programming language with low-level facilities. ...
Constraint logic programming
-
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. Bold textConstraint logic programming is a form of constraint programming, in which logic programming is extended to include concepts from constraint satisfaction. ...
Logic programming (sometimes called logical programming) is programming that makes use of pattern-directed invocation of procedures from assertions and goals. ...
Backtracking is a strategy for finding solutions to constraint satisfaction problems. ...
Prolog is a logic programming language. ...
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. Logic programs are sometimes converted to constraint programs since a constraint solving program may perform better than a logic derivation program, and it might be desirable to perform this translation before executing a logic program. Logic programming (sometimes called logical programming) is programming that makes use of pattern-directed invocation of procedures from assertions and goals. ...
In computability theory a programming language or any other logical system is called Turing-complete if it has a computational power equivalent to a universal Turing machine. ...
Look up translate in Wiktionary, the free dictionary. ...
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
Prolog is a logic programming language. ...
The French 1999 eclipse An eclipse (Greek verb: ekleipô, to vanish, though it derives from the prefix ex-, away from, and Greek leipein, to leave) is an astronomical event that occurs when one celestial object moves into the shadow of another. ...
GNU Prolog A Native Prolog Compiler with Constraint Solving over Finite Domains GNU Prolog is a free Prolog compiler with constraint solving over finite domains developed by Daniel Diaz. ...
Domains 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
- 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. In abstract algebra, a Boolean algebra is an algebraic structure (a collection of elements and operations on them obeying defining axioms) that captures essential properties of both set operations and logic operations. ...
The integers are commonly denoted by the above symbol. ...
In mathematics, a rational number (or informally fraction) is a ratio of two integers, usually written as the vulgar fraction a/b, where b is not zero. ...
Linear algebra is the branch of mathematics concerned with the study of vectors, vector spaces (also called linear spaces), linear transformations, and systems of linear equations. ...
The word linear comes from the Latin word linearis, which means created by lines. ...
To do: 20th century mathematics chaos theory, fractals Lyapunov stability and non-linear control systems non-linear video editing See also: Aleksandr Mikhailovich Lyapunov Dynamical system External links http://www. ...
In mathematics, a set is called finite if there is a bijection between the set and some set of the form {1, 2, ..., n} where is a natural number. ...
Operations Research, or simply OR is an interdisciplinary science which deploys scientific methods like mathematical modeling, statistics, and algorithms to decision making in complex real-world problems which are concerned with coordination and execution of the operations within an organization. ...
Finite domain solvers are useful for solving constraint satisfaction problems, and are often based on arc consistency or one of its approximations. Constraint-satisfaction problems or CSPs are mathematical problems where one must find states or objects in a system that satisfy a number of constraints or criteria. ...
Arc consistency and path consistency are properties of constraint satisfaction problems. ...
The syntax for expressing constraints over finite domains depends on the host language. The following is a program (of what programming language?) that solves the classical alphametic puzzle SEND+MORE=MONEY in constraint logic programming: Verbal arithmetic, also known as cryptarithmetic, crypt-arithmetic, or cryptarithm, is a type of mathematical game consisting of a mathematical equation among unknown numbers, whose digits are represented by letters. ...
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 awaken: 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. In constraint satisfaction, local consistency conditions are properties of constraint satisfaction problems related to the consistency of subsets of variables or constraints. ...
Concurrent Constraint Programming Some popular concurrent constraint programming languages are: Image File history File links Wiki_letter_w. ...
Imperative constraint 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)
- Disolver (C++ library, proprietary)
- Gecode (C++ library, free software: X11 style)
- ILOG CP (C++ library, proprietary)
- Koalog Constraint Solver (Java library, proprietary)
- Minion (C++ program, GPL)
- Comet (C style language for constraint programming, GPL)
Java is an object-oriented programming language developed by Sun Microsystems in the early 1990s. ...
C++ (IPA pronounciation: ) is a general-purpose, high-level programming language with low-level facilities. ...
Minion is a solver for Constraint Problems. ...
External links |
Feeds |
Contact