The first generation of constraint programming languages focussed on a single technique: constraint propagation, as described in section 4 of [Wal97]. Whilst constraint propagation has proved itself on a variety of applications, it cannot alone suffice to efficiently produce solutions for typical practical industrial problems.
Over the years Operations Researchers have designed highly efficient
algorithms for several classes of problems, such as set partitioning,
matching, knapsack, and network flow problems,
using techniques based on Mixed Integer Programming (MIP).
More recently stochastic techniques, such as Simulated Annealing,
have achieved striking results on optimisation problems such as the
travelling salesman problem.
ECLiPSe is designed to take advantage of all these results, by supporting industrial scale MIP functionality, and stochastic techniques, as well as constraint propagation and solving.
More importantly, real industrial problems seldom fit into a specific class: the pure travelling salesman problem rarely comes up in real life because there are typically many salesmen available to cover the different customers, certain customers can only be visited at certain times of day, also roads are busier at certain times of day so the journey time may vary with the time of day, and anyway the poor salesmen need some time to rest - they can't usually complete their circuits before lunchtime! These ``side constraints'' may belong to another problem class - such as the class of set covering problems, or scheduling problems.
Industrial problems typically have constraints that belong to different problem classes - they are in a sense ``hybrid''. Accordingly it is not only necessary to offer a wide choice of algorithms for solving such problems, but also the facility to mix and match the algorithms, i.e. to build hybrid algorithms.
ECLiPSe is designed to support the fast development of specific hybrid algorithms tuned to the problem at hand. It is not assumed that the first algorithm implemented by the application developer is guaranteed to be the best one: rather ECLiPSe provides a platform supporting experimentation with different hybrid algorithms until an appropriate one is found which suits the particular features of the application.
In the next section we shall explore ECLiPSe as a problem modelling language. We distinguish two kinds of model: the conceptual model, which captures the problem specification, and the design model, which is tuned for efficient solving on a computer. ECLiPSe is designed to support both kinds of models, and the mapping between them.
In the following two sections we shall examine the ECLiPSe facilities for handling constraints. In [Wal97] we encountered different kinds of constraints - primitive constraints, propagation constraints and constraint agents. ECLiPSe supports various classes of built-in constraints, both primitive constraints and propagation constraints. ECLiPSe also allows complex constraints and constraint behaviours to be constructed from the built-in classes, thus supporting constraint agents.
After constraint handling we return to the second major aspect of problem solving: the search for solutions.
We will separate this discussion into two subsections. The first is concerned with constructive search, and the second with repair-based search. Constructive search explores the consequences of making choices for decision variables one-at-a-time. Each choice reduces the set of viable choices for the remaining decisions. By contrast repair-based search explores the consequences, not of making decisions, but of changing them. In this case the new choice is typically compared with the previous one, in the context of other suggested choices for the other decision variables. Initially it is not expected that the suggested choices are necessarily consistent with the constraints. The idea of changing the choices is to reduce the number of constraint violations until all the constraints are finally satisfied.
Finally there is a brief section on the ECLiPSe system, its external communication facilities, embeddability, documentation and how to obtain the system.