Mark Wallace, Stefano Novello, Joachim Schimpf
Contact address: IC-Parc,
William Penney Laboratory, Imperial College, LONDON SW7 2AZ.
email: mgw@doc.ic.ac.uk
August 1997
This paper introduces the Constraint Logic Programming (CLP) platform ECLiPSe. ECLiPSe is designed to be more than an implementation of CLP: it also supports mathematical programming and stochastic programming techniques. The crucial advantage of ECLiPSe is that it enables the programmer to use a combination of algorithms appropriate to the application at hand. This benefit results from the ECLiPSe facility to support fine-grained hybridisation.
ECLiPSe is designed for solving difficult "combinatorial" industrial problems in the areas of planning, scheduling and resource allocation. The platform offers a conceptual modelling language for specifying the problem clearly and simply, in a way that is neutral as to the algorithm which will be used to solve it. Based on the conceptual model it is easy to construct alternative design models, also expressed in ECLiPSe. A design model is a runnable program, whose execution in ECLiPSe employs a specific combination of algorithms. Thus the platform supports experimentation with different hybrid algorithms.
Technically the different classes of algorithms mentioned above have two aspects: constraint handling, and search. Various different constraint handling facilities are available as ECLiPSe libraries. These include finite domain propagation, interval propagation and linear constraint solving. In ECLiPSe the same constraint can be treated concurrently by several different handlers.
With regard to search behaviour, CLP and also mathematical programming typically impose new constraints at lower levels in the search tree. By contrast, stochastic techniques search for good solutions by locally repairing an original solution, and repeating the process again and again. ECLiPSe supports both kinds of search, and allows them to be combined into hybrid search techniques.