MIP search can be duplicated in ECLiPSe by
passing the linear constraints to CPLEX and using the proposed
solutions to decide which new constraint to impose (i.e. guess) next.
Whilst there is little point in precisely duplicating the MIP search
control with ECLiPSe, it allows the ECLiPSe programmer to define new search
techniques using information from both the *fd* library and from
*eplex*.

For example the size of the finite domain, as recorded in the
finite domain library, can be used when choosing the next variable on
which to guess a constraint.
Then the value of this variable in the relaxed optimum returned from
*eplex* can be used when choosing to which value to label it
first.

This search technique is supported by the ECLiPSe library *fdplex*,
and is illustrated below.

The:- lib(fdplex). mylabeling([]). mylabeling(Vars) :- deleteff(Var,Vars,Rest), indomain(Var), mylabeling(Rest). solve(X,Y,Z,W) :- [X,Y]::1..5, [Z,W]::1..100, 10*Z+7*W+4*X+Y #= 49, Cost #= Z-2*W+X-2*Y, minimize(mylabeling([X,Y,Z,W]),Cost).Search with thefdplexLibrary

In query 1 the[eclipse 1]: [fdplexsearch]. * fd loaded * range loaded * eplex loaded * fdplex loaded * yes. [eclipse 2]: spy(mylabeling), spy(indomain). * spypoint added to mylabeling / 1. * spypoint added to indomain / 1. * yes. [eclipse 9]: solve(X, Y, Z, W). * CALL mylabeling([X{eplex:1.0, range : 1..5, fd:[1..5]}, * Y{eplex:5.0, range : 1..5, fd:[1..5]}, * Z{eplex:1.2, range : 1..3, fd:[1..3]}, * W{eplex:4.0, range : 1..4, fd:[1..4]}]) (dbg)?- leap * CALL indomain(Z{eplex:1.2, range : 1..3, fd:[1..3]}) (dbg)?- leap * EXIT indomain(1) (dbg)?- leap * CALL mylabeling([Y{eplex:5.0, range : 1..5, fd:[1..5]}, * X{eplex:2.0, range : 1..5, fd:[2..5]}, * W{eplex:3.7, range : 1..4, fd:[2..4]}]) (dbg)?- leap * CALL indomain(W{eplex:3.7, range : 1..4, fd:[2..4]}) (dbg)?- leap * EXIT indomain(4) (dbg)?- leap * CALL mylabeling([3, 2]) (dbg)?- no debug * Found a solution with cost -11 * X = 2 * Y = 3 * Z = 1 * W = 4 * yes.TracingfdplexSearch

Now *deleteff* selects the variable with the smallest
domain, which is *Z*.
The *fdplex indomain* predicate labels *Z* to the integer value
nearest to its value at
the relaxed optimum.
This wakes the *fd* constraint handler which tightens the domain
of *X*, and it wakes the linear solver which returns a new relaxed
optimum with new suggested values for the other variables.

This time the variable with the smallest domain is *W*, and this is
the one selected for instantiation.
Once this has been instantiated to the integer value closest to its
suggested value, *fd* propagation immediately instantiates the
remaining values.

At the next spy point the user enters *no debug* and tracing is
switched off.
The optimal solution is indeed the one found first, which testifies to
the usefulness of the combined heuristic used in the search.

Wed Sep 3 18:07:19 BST 1997