Branch and Bound (2)

Following up on the post from last time, which introduces a Python simulation of Branch and Bound for the problem shown above: the shortest path between points in 2D space.

Here is a bigger problem (N = 10). The points are:

0.142 0.748 0.38 0.98 0.547 0.498 0.834 0.283 0.242 0.916 0.848 0.432 0.109 0.474 0.828 0.964 0.066 0.574 0.274 0.839

The output is:

N = 10 3628800 possibilities i = 0 new smallest = 5.52 i = 2 new smallest = 5.205 i = 8 new smallest = 4.783 i = 19 new smallest = 4.774 i = 21 new smallest = 4.683 i = 99 new smallest = 4.666 i = 300 new smallest = 4.625 i = 324 new smallest = 4.238 i = 603 new smallest = 4.186 i = 627 new smallest = 4.174 i = 2244 new smallest = 4.128 i = 2256 new smallest = 3.746 i = 2262 new smallest = 3.734 i = 4114 new smallest = 3.495 i = 7284 new smallest = 3.326 i = 9520 new smallest = 3.274 i = 9640 new smallest = 3.262 i = 74468 new smallest = 3.226 i = 139466 new smallest = 3.185 i = 139476 new smallest = 2.952 i = 140647 new smallest = 2.943 i = 179796 new smallest = 2.842 i = 273364 new smallest = 2.778 i = 480496 new smallest = 2.776 i = 1038668 new smallest = 2.697

I recorded the iteration and value at which we obtained a new shortest path. At the bottom, the results are compared for a total enumeration (first) and then the branch and bound result. The timings indicate that the simulation is quite slow, and also that the algorithm isn't helping us much. I would bet that the reason is we don't abandon a putative solution until rather late in the calculation. Because the distances are too regular, our saved minimum value is not exceeded until close to the end.

min 2 8 7 0 5 4 9 3 1 6 2.697 58.8522 sec 2 8 7 0 5 4 9 3 1 6 2.697 44.89 sec

When I find a minute, I will modify the script to record when we bail from each calculation, and plot those as a histogram.

Also, it seems clear that this approach can only help us by some constant fraction of the total time. It doesn't really improve the crummy performance as N gets larger.

Code:

def try_all(N,D): smallest = N*1 retval = None for i,L in enumerate(permutations(range(N))): dist = total_distance(L,D) if dist < smallest: smallest = dist print 'i =', str(i).rjust(7), print 'new smallest =', round(smallest,3) retval = repr(L,dist) return retval def branch_and_bound(N,D): smallest = N*1 retval = None for L in permutations(range(N)): dist = total_distance(L,D,n=smallest) if not dist: continue if dist < smallest: smallest = dist retval = repr(L,dist) return retval def partTwo(): N = 10 A,D = init(N) plot(A,D) print 'N = ', N print math.factorial(N), 'possibilities' then = time.time() retval = try_all(N,D) now = time.time() print print 'min' print retval print round(now-then,4), 'sec' then = now retval = branch_and_bound(N,D) now = time.time() print retval print round(now-then,2), 'sec' if __name__ == '__main__': #partOne() partTwo()