HOME | Japanese Version

last update: 28 March 2006

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 quot;the processing direction is not fixed.quot;  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.

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

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.

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.

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.

What Are Weak Points ?

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

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.

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.

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.


Copyright(C) 2001-2006 by NTT DATA SEKISUI SYSTEMS CORPORATION. All rights reserved.