next up previous contents
Next: Constraint-Programming Language Interfaces Up: What is Constraint (Logic) Previous: Constraints as (Extended) Equations

Why Constraints and Programming?

There are some practical problems when using constraints (viewed as extended equations) alone to solve some real-life problems. As the set of equations is commonly static, it must be defined once for every problem. Usually there are decisions to be made while solving the problem, and those decisions can be dynamic in that they are not known beforehand; they have to be somehow anticipated for every set of initial data. Even if those decisions can be encoded as formulae (using special variables) the resulting mathematical model is often unnatural and difficult to solve. C(L)P addresses this problem with a series of programming facilities as, for example, search.

Sometimes there is a hierarchy of preferences which defines mandatory constraints, or imposes a penalty for constraint violation. Sometimes these penalties are not easy to determine (because, for example, the user has only some limited knowledge about the relative importance). Sometimes the penalties might change dynamically and be different for every problem instance. A programming-based approach tackles this by, for example, placing some rules before others, or incorporating some heuristics to the program which sets up the constraints.

It is not uncommon that large problems can be split into smaller, easier to work out tasks, such that solving and combining their results is cheaper than solving the whole problem at once. While solving equations is normally a process which takes into account all the available data at the same time, divide-and-conquer is a widely used programming technique which can as well be used to set up constraints -- and to help solve them faster.

Constraint-enriched languages inherit very interesting capabilities: they offer for free data abstraction, with which modules aimed at solving well-defined problems (which, in this scenario, involves setting up constraints among variables) can be written. Also, dedicated algorithms can be coded when an efficient way to solving the task at hand is known. Dynamic setting up of constraints has already been mentioned: what a C(L)P program does can be viewed as defining a skeleton of the equations needed to solve a class of problems, the particular instance being generated from the input data. And, last, a program-based approach allows runtime external communication (with the user, with other programs, with databases), and reacting adequately to the conditions of the environment. The actual constraint solver in the program is a black box (with, possibly, some switches which can be adjusted by the user) as in a OR tool.


next up previous contents
Next: Constraint-Programming Language Interfaces Up: What is Constraint (Logic) Previous: Constraints as (Extended) Equations
MCL
1998-12-03