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.

Wed Sep 3 18:07:19 BST 1997