Equations and inequalities between linear numeric expressions, as
defined in section 3.1 above, are a
subset of the constraints which can be handled by *ria*.
However this class can be handled very powerfully, so much so that any
inconsistency between the constraints is guaranteed to be detected.
Techniques for solving linear constraints have been at the heart of
operations research for half a century, and highly efficient linear
solvers have been developed.

One of the most widely distributed, scaleable and efficient packages incorporating a linear constraint solver is the CPLEX MIP package [CPL93]. CPLEX offers several algorithms for solving linear constraints including the Simplex and Dual Simplex algorithms. These algorithms are supported by sophisticated data structures, and the package can handle problems involving ten of thousands of linear constraints over ten of thousands of variables.

In the discussion so far, we have not yet mentioned an important aspect of most industrial combinatorial problems. Not only is it required to make decisions that satisfy the constraints, but they must also be chosen to optimise some measure. In the travelling salesman problem for example, the decisions of what order to visit the cities are based on optimising the total distance travelled by the salesman.

One feature of available packages for solving linear and mixed integer
problems, is support for optimisation.
figure is a design model for a transportation
problem, which uses the *eplex* library to pass the constraints
to the CPLEX package.

Note that, where:- lib(eplex). main(Cost, Vars) :- % Transportation problem: clients A,B,C,D, plants 1,2,3. % Variables represent amount delivered from plant to client. Vars = [A1, B1, C1, D1, A2, B2, C2, D2, A3, B3, C3, D3], Vars :: 0.0..10000.0, % variables A1 + A2 + A3 $= 200, % client demand constraints B1 + B2 + B3 $= 400, C1 + C2 + C3 $= 300, D1 + D2 + D3 $= 100, A1 + B1 + C1 + D1 $=< 500, % plant capacity constraints A2 + B2 + C2 + D2 $=< 300, A3 + B3 + C3 + D3 $=< 400, optimize(min( % solve minimizing 10*A1 + 7*A2 + 11*A3 + % transportation costs 8*B1 + 5*B2 + 10*B3 + 5*C1 + 5*C2 + 8*C3 + 9*D1 + 3*D2 + 7*D3), Cost).A Design Model for a Transportation Problem

`#`

and `*`

, `$`

.
The answer returned by ECLiPSe is

C = 6600.0 V = [0.0, 200.0, 300.0, 0.0, 0.0, 200.0, 0.0, 100.0, 200.0, 0.0, 0.0, 0.0]

In fact MIP packages typically not only offer optimisation as a
facility, they insist on an optimisation function in the design model.
Therefore in illustrating the two examples where *ria* performed
badly, using instead the *eplex* library, we shall
insert a dummy optimisation function!
The use of *eplex* on these examples is shown in figure
3.4.

[eclipse 1]: lib(eplex). * eplex loaded [eclipse 2]: X+Y $=< 1, Z+X $=< 1, Y+Z $=< 1, X+Y+Z $>= 2, Opt $= 0, optimize(min(Opt),Cost). * no (more) solution. [eclipse 3]: X+Y $= 2, X-Y $= 0, optimize(min(X),Cost). * X = 1.0 * Y = 1.0 * Cost = 0.0 * yes. [eclipse 4]: X+Y $= 2, X-Y $= 0, optimize(max(X),Cost). * X = 1.0 * Y = 1.0 * Cost = 0.0 * yes.Linear Constraint Solving

Query 2 is the same set of constraints whose inconsistency is not
detected by *ria*.
*eplex*, however, recognises their inconsistency.

In order to establish that there is only one possible value for *X* we
have had to use two queries, 3 and 4, first finding the minimum value
for *X* and then the maximum.
Although the same value for *Y* was returned in both solutions, the
*eplex* library has still not proved that 1 is the only
possible value for *Y*.

For problems involving only real number (or *continuous*) variables,
linear constraint solving alone suffices to solve the problem.
However industrial problems typically include a mixture of real number
and integer variables.
For example in problems involving discrete resources the
decision as to
which resource to use for a task cannot be modelled as a continuous
variable.
Traditionally operational researchers will use a binary (or *0/1*)
variable or an integer variable.
Most resources are discrete, for example machines for jobs, vehicles
for deliveries, rooms for meetings, berths for ships, people for
projects, and so on.
Another fundamental use of discrete variables is in modelling the
decision as to which order to do things in - for example visiting
cities in the travelling salesman problem, or performing tasks on the
same machine.

From the point of view of the programmer, adding the constraint that a variable is integer-valued is straightforward. However the effect of such a constraint on the performance of the solver can be disastrous, because mixed integer problems are much harder to solve than linear problems!

[eclipse 1]: lib(eplex). * eplex loaded [eclipse 2]: X+Y $>= 3, X-Y $= 0, optimize(min(X), C). * Y = 1.5 * X = 1.5 * C = 1.5 * yes. [eclipse 3]: integers([X]), X+Y $>= 3, X-Y $= 0, optimize(min(X), C). * Y = 2.0 * X = 2 * C = 2.0 * yes.Mixed Integer Programming

The *eplex* library uses standard range-variables provided by the
range-library,
which facilitates interfacing to other solvers. The interface to CPLEX
enables
state information to be retrieved, such as constraint slacks, basis
information, and reduced costs.
Also many parameters can be queried and modified.
A quite generic solver demon is provided which makes it easy to use
CPLEX
within a data-driven CLP setting.

The notion of solver handles encourages experiments with multiple solvers. A pair of predicates make it possible to read and write problem files in MPS or LP format.

MIP packages such as CPLEX and XPRESS , which is also
currently being
integrated into the *eplex* package, are surprisingly effective
even for some problems involving many discrete variables.
Their underlying linear solvers reflect a carefully chosen balance
between flexibility and scaleability.
They offer less flexibility than the linear solvers which are usually
built
into constraint programming systems, such as *CLP*(*R*), but much better
scaleability.

It has proved possible, within ECLiPSe, to achieve much of the
flexibility of *CLP*(*R*) within the restrictions imposed by
MIP solvers [RWH97].

Wed Sep 3 18:07:19 BST 1997