constraint.org/HISTORY

last update: 28 March 2006

History of Research and Application

Constraint Programming has been researched actively from the 1980s around, and it entered the age of practical use in the 1990s. Also now the research on Constraint Programming and practical use are repeated.
Constraint Programming is researched all over the world. In Japan, this research is one of the main themes in ICOT and plenty of processing systems have been developed and the research has met with many good results. It is said that ICOT greatly contributed to the development of Constraint Programming research.
We retrace the development in every time briefly as follows.

Early Research (Till 1980 Around)

SketchPad (Sutherland, 1963) -- Interactive drawing tool. The most early constraint system.
Image Labeling (Waltz, 1972) -- was rediscovered as Constraint Solution Algorithm later.
ThingLab (Boring, 1981) -- Interactive drawing tool.
ALICE (1978) -- the lead of General Constraint Processing Systems

Active Research(The 1980s)

Constraint Programming became actively researched as an extension of Logic Programming and then General Constraint Processing System got to be developed. Therefore Constraint Programming is called Constraint Logic Programming in many cases.

ICOT (Japan)-- CAL, GDCC, CuProlog and so on. It is published in the software archive of AITEC now.
ECRC (European Institute for Joint Research) -- CHIP. It became the basis of commercial Constraint Processing Systems such as Charme,CHIP V4.
University of Marseille(France)-- PrologIII. By the developer of Prolog.
Monash University(Australia), IBM Watson Research Center(U.S.A) -- CLP(R).

Age of Practical Use(The first half of The 1990s)

Constraint Processing System for business was developed and sold.
In Japan, the following systems were sold.

Charme (made by Bull S.A., France, sold by ISAC, Inc.) -- Charme is the first Constraint Processing System for business in the world. It is based on the results of CHIP of ECRC.
CHIP V4 (made by Cosytec, France, sold by CRC Solutions Corp.) -- It is made for business based on CHIP of ECRC.
ILOG Solver (made by ILOG S.A., France)-- ILOG Solver is a library of C++ and a successor to library PECOS for Lisp of ILOG.
IF Prolog (made by IF Computer GmbH., Germany, developed by Siemens AG, Germany) -- is based on SRI-Prolog developed by Siemens, Germany. It is descended from CHIP of ECRC.

These are all general environments for software development and they were mainly used for developing the applications for the scheduling problems such as personnel scheduling, production scheduling and transportation scheduling, and design problems.

We can regard CHIP and IF Prolog as extensions of Prolog. However concerning Charme, two versions---an interpreter of Non-procedural Language with original syntax and C library---were provided. ILOG Solver is a class library of C++. As a whole they are in the framework of Constraint Logic Programming, but they can be used in Procedure-oriented Language and it becomes easy to integrate with other systems.

On the other hand, the research for making parallel was mainly improved and the research for integrating with other paradigms beyond the range of Logic Programming became also active. In Europe, Parallel Constraint Programming was researched especially as a part of ESPRIT Project and many results were obtained.
For example, the research results in this period are as follows.

Concurrent Constraint (Saraswat, 1994) -- is the formalization of Parallel Constraint Programming and the starting point of later researches.
AKL (Sweden SICS) -- The base is Andorra Kernel model as Parallel Logic Programming model. It is said to be the pioneering result of the research for integrating paradigms such as Parallel Constraint Logic Programming, Functional Programming Language, Object-oriented.
Oz (Germany DFKI) -- is the language with original syntax and started being developed at this period. Thereafter it was developed by SICS and Catholic University of Louvain together and grew to Mozart that is a programming environment for multi-paradigm to integrate Parallel Constraint Logic Programming, Functional Programming Language, Object-oriented and Distributed Programming. It continues till present.

The Latest Trend

The performance of computer hardware improves remarkably. In the early years of the 1990s when hardware started to be commercialized, memory was increased on an expensive WS. But as very low-priced PCs with the much higher performance than the then WS became popular, and at last Constraint Programming became the technology that is commonly used.
The temporary rush to commercialize Constraint Programming has passed. After that the results of developing practical applications based on Constraint Programming steadily accumulated and thus they especially grew to be one of the basic technologies for constructing the planning systems.
SCM (Supply Chain Management) has lately attracted attention in particular and the planning system that is the main application area of Constraint Programming has been spotlighted. The scheduling system that executes scheduling with considering the complicated constraint requirements is particularly called APS and distinguished from the usual systems. Constraint Programming is used as one of the methods to materialize this APS.
TOC or Bio-oriented Production System, which are the way to think and the method paying attention to “Constraint” in a wide sense, attract attention.
On the other hand, the graphical side of system is noticed in parallel with the spread of JAVA language. Also JAVA Language Library, and the processing systems in which JAVA language is extended are made.
The number of the systems with Constraint Solver increases in Prolog processing systems.
The researches for making multi-paradigm such as fusion with Functional Programming Language are made and moreover the research like Phase Transitions in Search is also carried. The importance of Constraint Programming seems to increase more and more in future.

HOME | TOP