Many familiar UNIX tools have aspects of constraint programming. The regular expressions used in awk, grep, lex, and sed are all declarative (as opposed to imperative) in form. That is, they specify desired results, as opposed to particular courses of action.

An even stronger case can be made for tools like troff and, particularly, pic. troff interprets a set of formatting commands, molding text to fit within a set of document formatting constraints. Some of these are built into the program. Others, such as page size, are variable at run time.

Although raw troff is pretty imperative in nature, most users add a macro set such as me or ms, which makes the interface far more declarative. pic actually accepts specific placement constraints adding them to its own ideas about "attractive" drawings.

None of these tools and languages go very far in the direction of true constraint programming, however. Let's look at the definition in Alan Bundy's "Catalogue of Artificial Intelligence Techniques" (Springer-Verlag, 3rd ed., 1990):

This is a pretty open definition, and indeed, there are many kinds of constraint systems around. The kind of constraints a constraint language can solve is largely a function of the solution technique. For example, many constraint languages are built on top of Prolog, which uses goal-directed searching. The constraint system performs a high-level evaluation of the solution space, preventing the logic programming from evaluating legal, but unproductive paths.

Crypto-arithmetic problems such as "SEND + MORE = MONEY" are ideal for demonstrating constraint programming techniques. In such problems, each letter stands for a number, and the solution must determine a set of number-letter pairings that meet the stated equation.

A brute force search of all possible pairings would take a great deal of time. Constraint programming, in contrast, can trim the search tree substantially. In the example above, for instance, we know that either D+E=Y or D+E=Y+10 and that M must be one. Searching only those parts of the tree where conditions like these pertain, we can dramatically reduce the needed amount of calculation.

The field of linear programming answers a different sort of constraint solving need. Assume that you are tasked with managing a petroleum refinery. It can only produce certain combinations of chemicals, and the amounts are limited by physical limits such as flow rates.

If you know the market prices for the possible products, you should be able to determine the best possible product mix. Unfortunately, the solution involves finding the optimal point in a multi-dimensional solution space bounded by dozens or hundreds of linear inequalities.

The Simplex linear programming system takes advantage of the fact that the solution space must be convex. After ensuring that a feasable solution space really exists (that is, no inconsistent constraints are present), the algorithm uses a simple hill-climbing technique, Traversing vertices along the outside surface until no "better" neighboring vertex can be found.

Archives

Dozens of constraint programming systems are available on the Internet. The definitive starting point is the Frequently Asked Questions file for the newsgroup comp.constraints. Edited by Michael Jampel (jampel@cs.city.ac.uk), the FAQ is available as comp-constraints-faq ftp://ftp.cs.city.ac.uk/pub/constraints/. The FAQ contains useful definitions, annotated pointers to available resources, and more. WWW users may wish to go to the URL: http://web.cs.city.ac.uk/archive/constraints/constraints.html.

The directory also contains bibliographic information, references on linear and nonlinear programming, archives of the comp.constraints newsgroup, and more. I can't imagine a better starting point for a foray into the field.

References

Michael Jampel recommends Pascal Van Hentenryck's "Constraint Satisfaction in Logic Programming" (MIT Press, 1989, ISBN 0-262-08181-4). I like Wm Leler's "Constraint Programming Languages: Their Specification and Generation" (Addison-Wesley, 1988, ISBN 0-201-06243-7). The book provides a very useful overview of the field. It also introduces Leler's language BERTRAND, which is a tool for generating new constraint programming languages.

Much of the material for this column was derived from comp.constraints-faq. I also wish to thank Mark Kantrowitz (Mark_Kantrowitz@cs.cmu.edu), the archivist of the CMU AI Repository, for his useful pointers and explanations. Any mistakes in this column, as usual, are my own.