Subsections

• The OR Edge
• The CP Edge

Typical Applications and Approaches

As with any other computational approach, all problems are amenable to be tackled with C(L)P; notwithstanding, there are some types of problems which can be solved with comparatively little effort using C(L)P based tools. Those applications share some general characteristics:

• No general, efficient algorithms exist (NP-completeness): specific techniques / heuristics must be used. These are usually problems with a heavy combinatorial part, and enumerating solutions is often impractical altogether. A fast program using usual programming paradigms is often too hard and complicated to produce, and normally it is so tied to the particular problem that adapting it to a related problem is not easy.
• The problem specification has a dynamic component: it should be easy to change programs rapidly to adapt. This has points in common with the previous item: C(L)P tools have builtin algorithms which have been tuned to show good behavior in a variety of scenarios, so updating the program to new conditions amounts to changing the setting up of the equations.

• Decision support required: either automatically in the program or in cooperation with the user. Many decisions can be encoded in mathematical formulae, which appear as rules and which are handled by the internal solvers, so (although, of course, not always) there is no need to program explicit decision trees.

Among the applications with these characteristics, the following may be cited: planning, scheduling, resource allocation, logistics, circuit design and verification, finite state machines, financial decision making, transportation, spatial databases, etc.

$\mathbf\therefore$

Let us review some approaches to solving problems with the aforementioned characteristics:

Operations Research

systems, and also genetic algorithms, simulated annealing, etc., have a medium development effort, since most of the core technique (e.g., the solving algorithms themselves) are already coded an optimized, so the problem has only to be modeled and fed into the system. They have the drawback of being not flexible (equations cannot be updated dynamically), and heuristic search of solutions is not always easy to include in the problem, or the modification according to the desires of the user.

Conventional programs

can potentially give the most efficient solution, but this efficiency comes at a high cost: reaching a solution needs a uphill development phase, in which all solving--not only the particular problem conditions--has to be explicitly described; usually the solving/search part of the problem is tailored for the particular application (which accounts for the high performance of the program), which in turn makes the program not amenable to be adapted to other scenarios, even related ones. Success in this approach also requires a deep knowledge of constraint solving algorithms, which in CLP systems is built in.

Rule-based systems

receive a good rate in heuristic possibilities, but on the other hand they lack constraint solving capabilities, and an algorithmic style is difficult to embed.

Constraint-based approaches

especially when combined with Logic Programming, try to combine the best of all the previous points. Not only constraint solving is included as a part of the systems, but algorithmic components are provided for being used when needed (e.g., in the cases in which parts of a problem can be worked out more advantageously using an explicit algorithm). Also, this algorithmic part interacts with the constraint solving part by creating dynamically the equations to be solved, and communicating the solutions by means of the variables of the language. Also, rules as means of expressing heuristics are available when using logic programming-based constraint tools.

$\mathbf\therefore$

Since usual programming techniques are commonly well understood, we will review the tradeoffs between using Operation Research and Constraint Programming approaches:

The OR Edge

OR is a good approach when the problems to be solved have some specific characteristics:

• A good degree of staticity in the problem to be solved: the only differences among runs of the program are some coefficients which can be easily changed or tuned, and that in no way affect the modeling of the problem (which is the most difficult part to change).
• Can be expressed using classical, well-known OR models. This makes good, efficient algorithms available, and guidelines and examples for modeling the problem clear and well understood.
• The size of the problem (usually measured in the number of variables needed) is very large. If well suited OR methods are available, then probably they will be highly optimized, and then large problems could be solved within a reasonable amount of time.

The CP Edge

CP has short development time, flexibility, and good efficiency as main advantages:

• Fast prototyping is easy with CP; preliminary models of the problem, often working correctly as reduced versions of the final program are fast to build. The program evolves through successive refinements, in which experiments to find the best approach can be performed.
• Flexibility, adaptability, and maintainability are also strong points in favor of constraint programming. Due to the dynamic equation set up, the code tends to be adaptable, easy to change, and to maintain: conditions are not encoded directly in the equations, but rather in the way they are created.
• The performance of CP systems is good: in fact, internal solving algorithms are usually very optimized (in most cases they are inherited from O.R.), and can deal with sizeable problems exhibiting a reasonably good performance. The fact that prototyping is fast also adds to the global performance of the approach, and since successive refinements are used to reach to a solution, there is no need to perform a complete rewriting of the code to obtain a ``robust'' production program.