The eplex library allows an external Mathematical Programming solver to be
used by ECLiPSe. It is designed to allow the external solver to be seen
as another solver for ECLiPSe, possibly in co-operation with
the existing `native' solvers of ECLiPSe such as the ic solver. It is
not specific to a given external solver, with the differences between
different solvers (largely) hidden from the user, so that the user can
write the same code and it will run on the different solvers.
The exact types of problems that can be solved (and methods to solve them)
are solver dependent, but currently linear programming, mixed integer
programming and quadratic programming problems can be solved.
The rest of this chapter is organised as follows: the remainder of this
introduction gives a very brief description of Mathematical Programming, which
can be skipped if the reader is familiar with the concepts.
Section 16.3 demonstrates the modelling of an MP problem, and the
following section discusses some of the more advanced features of the library
that are useful for hybrid techniques.
16.1.1 What is Mathematical Programming?
Mathematical Programming (MP) (also known as numerical optimisation) is the study of optimisation using
mathematical/numerical techniques. A problem is modelled
by a set of simultaneous equations: an
objective function that is to be minimised or maximised, subject to a set of
constraints on the problem variables, expressed as equalities and
Many subclasses of MP problems have found important practical
applications. In particular, Linear Programming (LP)
problems and Mixed Integer Programming (MIP) problems are perhaps the most
important. LP problems have both a linear objective function and linear
constraints. MIP problems are LP problems where some or all of the
variables are constrained to take on only integer values.
It is beyond the scope of this chapter to cover MP in
any more detail. However, for most usages of the eplex library, the user
need not know the details of MP – it can be treated as a black-box
- For more information on Mathematical Programming, you can read a
textbook on the subject such as H. P. Williams' Model Building in
Mathematical Programming .
Linear Programming (LP) problems: linear constraints and objective
function, continuous variables.
- Mixed Integer Programming (MIP) problems: LP problems with some or
all variables restricted to taking integral values.
Figure 16.1: Classification of MP problems
16.1.2 Why interface to Mathematical Programming solvers?
Much research effort has been devoted to developing efficient ways of
solving the various subclasses of MP problems for over 50 years. The
external solvers are state-of-the-art implementations of some of these
techniques. The eplex library allows the user to model an MP problem in
ECLiPSe, and then solve the problem using the best available MP tools.
In addition, the eplex library allows for the user to write programs that
combines MP's global algorithmic solving techniques with the local
propagation techniques of Constraint Logic
16.1.3 Example formulation of an MP Problem
Figure 16.2 shows an example of an MP problem.
It is a transportation problem where
several plants (1-3) have varying product producing capacities that must
be transported to various clients (A-D), each requiring various amounts of
the product. The per-unit cost of transporting the product to
the clients also varies. The problem is to minimise the transportation
cost whilst satisfying the demands of the clients.
Figure 16.2: An Example MP Problem
To formulate the problem, we define the amount of product transported from
a plant N to a client p as the variable Np, e.g. A1
represents the cost of transporting to plant A from client 1. There are
two kinds of constraints:
The objective is to minimise the transportation cost, thus the objective
function is to minimise the combined costs of transporting the product to
all 4 clients from the 3 plants.
The amount of product delivered from all the plants to a client must be equal to the
client's demand, e.g. for client A, which can recieve products from plants
1-3: A1 + A2 + A3 = 21
- The amount of product sent by a plant must not be more than its
capacity, e.g. for plant 1, which can send products to plants A-D:
A1 + B1 + C1 + D1 ≤ 50
together, we have the following formulation of the problem:
min(10A1 + 7A2 + 200A3 + 8B1 + 5B2 + 10B3 + 5C1 + 5C2 + 8C3 + 9D1 + 3D2 + 7D3)
|A1 + A2 + A3
|B1 + B2 + B3
|C1 + C2 + C3
|D1 + D2 + D3
|A1 + B1 + C1 + D1
|A2 + B2 + C2 + D2
|A3 + B3 + C3 + D3