next up previous contents
Next: Incomplete Constructive Search Up: Constructive Search Previous: MIP Search

Search Heuristics based on Hybrid Solvers fdplex

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.

:- 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 the fdplex Library  
The fdplex version of indomain selects the value closest to the value at the relaxed optimum returned by eplex. Indeed it is instructive to watch the search taking place using the ECLiPSe tracing facilities, so we shall load the program of figure gif into a file called fdplexsearch.pl. Now we shall run it as shown below.
[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.
Tracing fdplex Search  
In query 1 the fdplex is loaded, and it automatically loads the other libraries which are needed. Query 2 sets spypoints on two predicates. Now each time either of these predicates are called, and when they exit, the debugger stops and allows the programmer to study the state of the program execution. Query 3 calls the program defined in figure gif. Before labelling starts the domains of the variables have already been reduced by finite domain propagation. The reduced domains are automatically communicated to the range library, and passed into the linear solver. The linear solver (CPLEX) has already been invoked by eplex and has returned the values of the variables X,Y,Z,W at the relaxed optimum.

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.


next up previous contents
Next: Incomplete Constructive Search Up: Constructive Search Previous: MIP Search

Joachim Schimpf
Wed Sep 3 18:07:19 BST 1997