Like several other areas in current computer science, constraint processing sees Ivan Sutherland's 1963 Sketchpad project as a precursor. It has inspired G. Sussman and G. Steele to develop a language called CONSTRAINTS. Alan Borning continued Sketchpad with his ThingLab at PARC. Since then Borning and his group have continued developing the algorithms that make it possible for users to solve their problems without specifying any algorithms.
I call this line of research point-based constraint processing. It works by assuming individual values for the variables. With each type of constraint and each of its arguments there is associated an algorithm for adjusting the value of the variable to satisfy that constraint. This is a local adjustment. By iterating this computation for all arguments of all constraints, one hopes to converge on a global result: a combination of values for all variables that satisfies all constraints. This iteration is called constraint propagation. Algorithms for this are of crucial importance for the success of constraint processing.
Another approach to solving a problem posed in terms of constraints is set-based constraint processing. Here one associates with each variable a set, called domain, of candidate values. In addition, one associates with each constraint an operation that removes values from the domains of the variables related by this constraint that are inconsistent with that constraint. This operation is called the contraction operator of the constraint. Now the local adjustment consists of applying a constraint's constraction operator. Constraint propagation consists of applying the contraction operators of sufficiently many constraints sufficiently many times to obtain convergence. The aim of algorithms for constraint propagation is to obtain convergence with as few applications of contraction operators as possible.
The Davis-Putnam procedure determining Boolean satisfiability can be viewed as an example of set-based constraint propagation. The CHIP language extended Prolog with this variant of constraint processing for solving a wide variety of constraint satisfaction problems with discrete domains. If one wants to model systems where variables are continuous, then the domains are sets of real numbers. Intervals with floating-point numbers as bounds are a sufficiently rich collection of such sets that is also efficiently representable in a computer. When the domains are such intervals, we have interval constraints.
Problems of numerical computation can be formulated as interval constraint problems. It turns out that solving them in this way has several advantages over conventional methods. For instance, that they actually get solved.
Modified September 10, 2002