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.
:- 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
Note that, where fd uses a # and ria uses a *,
eplex uses a $.
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].