Re: [eclipse-users] Minimum cost path and branch-and-bound

Joachim Schimpf (Independent Contractor) wrote:
> Francesco Santini wrote:
>> Hi everybody,
>>
>> I am an ECLiPSe newbie even if I have some experience with Prolog.
>> I need to compute the minimum cost path from a node A to a node B.
>> My Prolog code could be something very simple like:
>>
>> -
>> edge(n0, n1, 1).
>> edge(n1, n2, 6).
>> edge(n1, n3, 2).
>> edge(n1, n4, 3).
>> edge(n2, n4, 5).
>> edge(n3, n5, 9).
>> edge(n3, n6, 5).
>> edge(n4, n5, 2).
>> edge(n4, n9, 3).
>> edge(n5, n7, 1).
>> edge(n5, n8, 1).
>>
>> path(X, Y, C):-
>>   edge(X, Y, C).
>>
>> path(X, Y, C):-
>>   edge(X, Z, C1),
>>   path(Z, Y, C2),
>>   C is C1 + C2.
>>
>> allpath(X, Y, L):-
>>   findall(C, path(X, Y, C), L).
>> -
>>
>> Given the query: allpath(n0,n9,L) it returns the list [15,7], i.e. the
>> list of the costs of all the possible paths going from n0 to n9.
>>
>> I would like to use ECLiPSe to apply the branch-and-bound technique to
>> the cost of the path in order to speed up the search (for a wider
>> network) and find the best path between two given nodes (minimum cost
>> path).
>> Clearly, replacing the above allpath clause with
>>
>> searchpath(X, Y, C):-
>>   bb_min( path(X, Y, C), C).
>>
>> (from library(branch_and_bound)) does not work 
> 
> Yes it does - have you not tried?
> 
> ?- bb_min(path(n0, n9, C), C, _).
> Found a solution with cost 15
> Found a solution with cost 7
> Found no solution with cost -1.0Inf .. 6
> C = 7
> Yes (0.00s cpu)

Sorry, that answer was probably unhelpful...  Although it works, it
will not give you any speedup: the search tree will only be pruned
at its leaves, i.e. when a complete path to the destination has
been found and the cost variable becomes instantiated.

To get earlier pruning, you will indeed need to change the distance
computation to use constraints, so that the cost bound can be applied
to partially computed path costs.  Simply add
:- lib(ic).
for using the ic constraint solver.  Then you have to change the
"lazy" computation of the cost (after the choices have been done)
into an eager one (before the choices are done), by moving it to
the left and by using constraints instead of ground arithmetic:

path(X, Y, C):-
    C1 #>= 0, C2 #>=0,
    C #= C1+C2,
    edge(X, Z, C1),
    path(Z, Y, C2).

If you now run bb_min(path(n0, n9, C), C, _) with the Query->PortProfile
option in tkeclipse, you can see that the number of calls (and exits) to
edge/3 has been reduced significantly:

PREDICATE       CALLER            call  exit  fail *exit  redoresume delay  next
edge        /3  path        /3      24     7    17     6     6     .     .     2
compared to the naive code:
edge        /3  path        /3      36    11    25     8     8     .     .     .

In your example, calls to edge/3 correspond to nodes of the search tree.


-- Joachim