Constraint Programming

What Is Constraint Programming?

Constraint Programming can be regarded as the programming paradigm that aims at

"Computer finds the answer satisfying constraints when giving a problem as an aggregate of constraints to computer."

It is important to distinguish the description of constraint problem from the procedure and the way to solve a problem. Describing a problem with constraint has the "declarative" character. The important feature of constraint is "the processing direction is not fixed." We can consider that this feature is the character of complete "declaration".
On the other hand, there may be various ways to solve problems. But on Constraint Programming in a narrow sense, the target for researches is the technique to efficiently find answers by well using the constraints in the problem. The program to find the solution satisfying constraints is called Constraint Solution System or Constraint Solver. The actual algorithm for Constraint Solution depends on the kind of constraint (what type of constraint against what type of variable).

What Is Not Constraint Programming? -- Related Field

Under the definition mentioned above, the concrete algorithm is not specified for "How to solve a problem." Therefore in a wide sense, a large number of areas are included. For example, the solution methods of Constraint Satisfaction Problem (CSP) can be given easily as follows.

  • Various algorithms, Linear Programming, Newton method, Dynamic Programming etc., which have been researched by Operations Research (OR).
  • Various techniques based on Tree Reference.
  • Techniques based on constraint rewriting such as the merging method or condensing by the programming conversion.
  • Algorithms for Solution Improvement such as minimum-conflict, taboo search, Simulated Annealing(SA)
  • Search by using neural network
  • Genetic Algorithm(GA)

The follows can be given as Constraint Paradigm in a wide sense.

  • Theory of Constraint (TOC) that attracts notice because of SCM and so on.
  • Syntax theory (HPSG, Constraint Grammar etc.)  based on constraint in Natural Programming Language Processing

It is meaningless to strictly define Constraint Programming, because there are various viewpoints toward "What is Constraint Programming or not". However the following points can be generally given as for the center point of the area covered by Constraint Programming.

  • Constraint is not limited to a numerical value.  The problem is treated as a constraint irrespective of a computational area of problem.
  • The central technology is the effective algorithm to keep matching by detecting a contradiction included in the problem space.
  • Tree search is the base for searching solution and thus the basis is reducing a search space by positively using constraints when searching.

The especial important point seems to be the paradigm-like side, on which Constraint Programming handles the problem as a constraint regardless of the computational area of problem.
To be concrete, only the specific area out of the computational areas is focused on, researched and applied.  When the superior technique is suggested in the related area, the paradigm based on constraint can be given as a framework for taking in such a technique.
In this sense, Constraint Programming in a wide sense plays a part as a node to connect the techniques that have researched in various fields.
Therefore this site will take up not only Constraint Programming in a narrow sense but also paradigm for Constraint Satisfaction Problem (CSP) in a wide sense and Constraint Paradigm as possible.

The Word, "Constraint Logic Programming" Has Ever Been Heard ...

Constraint Logic Programming is what the above Constraint Programming is realized as an extension of Logic Programming. Logic Programming has many features jointly with Constraint Programming and so Logic Programming can be said to be a part of Constraint Programming.  Actually a lot of prolog programming systems, which are the representative of Logic Programming Languages, have constraint solvers at present. Many systems for Constraint Programming are based on the idea of Logic Programming even if they are always not based on Prolog.  Constraint Programming in a narrow sense can be said to be the same as Constraint Logic Programming.

What Are Features of Constraint Programming ?

Constraint Programming has the features as follows.

  • It is declarative and does not fix the information flow in one direction.
  • The definition of constraint solution and the solution method vary according to the target area to be constrained.
  • Efficiently searching is expected by using constraints.
  • Prototyping is easy. Development productivity is high.
  • It has a close affinity with Object-oriented Paradigm.

Declaration is the most notable feature of Constraint Programming. This feature is related to separation of the problem definition and the solution method. Functional Programming and Logic Programming also have the feature as declaration. However in Functional Programming, the information flow is fixed. The information flow in Logic Programming Language used to be fixed in point of implementation. Of course, what the flow of information can be fixed is profitable for efficiently solving problems in many cases. Besides it is not necessarily true that interactivity is available all the time.  However Constraint Programming can be said to be the most thorough concerning declaration.

Moreover, the efficient problem solution is considered in point of efficiently searching by using constraint. As the definition of constraint solution and the solution method vary according to the target area to be constrained, constraint solver must be provided for every target area.  Conversely, Constraint Programming can be considered very flexible and open because various efficient solutions can be gathered in the framework of Constraint Programming.

The features that prototyping is easy or development productivity is high owe a great deal to declaration. Besides when the constraint is regarded as the relation between objects, it is expected that Constraint Programming have a close affinity with object-oriented paradigm.  Actually many Constraint Processing Systems are objected-oriented.

Is Constraint Programming Practical ?

Constraint Programming is one of the basic technologies for developing various practical systems, and applicable for various fields. Almost ten years have passed since commercial systems were sold.  During that time, a lot of practical systems have been developed based on Constraint Programming and applied.
See Application for the application fields and see Report for the actual examples.

What Are Superior Points ?

The following points are given as an advantage of Constraint Programming. Some are the same as the features.

  • Constraint Programming is declarative therefore description of a problem to be solved can be concentrated upon without supposing the specific method to solve a problem.
  • Constraint Programming can become the frame for constructing the system that can use various solutions appropriately.

What Are Weak Points ?

On the other hand, the followings are given as weak points of Constraint Programming.

  • What Constraint Programming is declarative means that the operation cannot be expected only by seeing a program.  Constraint Programming cannot operate after writing like Procedure-oriented Language does.  Furthermore declaratively writing is not easy to write at any time.
  • The approach with searching in a wide area makes the efficient search by solving constraint, but the cost of time and space for getting a solution may be too great.

Why Is Constraint Programming Unpopular ?

As mentioned above, Constraint Programming has only not merits but also demerits. However why is Constraint Programming unpopular?  The following points are given.

  • Environments such as hardware were too poor to operate Constraint Programming and Constraint Programming was an "expensive" technology.
  • The side as an extension of Logic Programming was emphasized too much and Constraint Programming tended to be considered indivisible from Logic Programming Language.

Actually in the early days when Constraint Programming was put in practical use, it seemed to be advertised by emphasizing the side as the most advanced technology.  Therefore commercial tools were very expensive; they could be used only for large-scale projects.

But now, a time changes and the present situations are as follows.

  • The performance of hardware makes rapid progress. At first, Constraint Programming could be used only on an expensive workstation. But now Constraint Programming can be used on the PC that exceeds the then workstations in performance and is low-priced.
  • Although Constraint Programming can be considered to be an extension of Logic Programming, it is not necessary to suppose the specific implementation of Logic Programming. Indeed Constraint Processing System has been implemented as a library on Procedure-oriented Language (especially Object-oriented Language), not an extension of Logic Programming.  In addition it has been proved that a lot of practical application could be constructed.

Constraint Programming technology is still young. So the time from now when the conditions have been ready may be the age of real practical use.