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. 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.
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 finite sets
- Mixed domains, involving two or more of the above
Constraint languages are typically embedded in a host language. The first host language used was a logic language (Prolog), so the field was initially called Constraint Logic Programming. The two paradigms share many important features, like logical variables (i.e., once a variable is assigned a value, it cannot be changed), backtracking. Nowadays, most Prolog implementations include one or more libraries for constraint logic programming.
Constraint programming can be realised as either a dedicated language, or as a library to be used in a regular programming language.
Some popular constraint 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, proprietary)
- Mozart (Oz based, Free software: X11 style)
- SICStus (Prolog based, proprietary)
Some popular libraries for constraint programming are:
- Choco (Java library, Free software: X11 style)
- Disolver (C++ library, proprietary)
- Gecode (C++ library, X11 style)
- ILOG Solver (C++ library, proprietary)
- Koalog Constraint Solver (Java library, proprietary)
Finite Domain
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 (see AC-3 algorithm), or one of its approximations.
The syntax of CP(FD) languages depends on the host language. The following is a program that solves the puzzle SEND+MORE=MONEY in CLP (i.e., Constraint Programming based on a logic language):
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 constraint solver creates the variables, and the domains, so all the variables range over the set of values {0,1,2,3, ..., 9}. S#\=0 (which means ) is imposed, and value 0 is removed from the ___domain of variable S. Same for variable M. Then, the constraint alldifferent(Digits) is imposed: it cannot propagate any deletion, so it simply suspends. Then the last constraint is imposed. From the last constraint, the solver infers that M=1. All the constraints involving variable M are awaken: in particular alldifferent can remove value 1 from the ___domain of all the remaining variables. When the AC-3 algorithm reached quiescence, the domains have been reduced, and the problem is hopefully easier to solve.
Predicate labeling starts the depth first search: it takes the first value in the ___domain of the first variable, and assigns it to the variable. Then, the AC-3 algorithm is resumed and performs further ___domain reductions. If one ___domain becomes empty, labeling backtracks and tries the second value in the ___domain of the first variable. Otherwise, it tries the first value in the ___domain of the second variable, and so on, until a solution is found.