## Wednesday, March 24, 2010

### 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 = 103628800 possibilitiesi = 0 new smallest = 5.52i = 2 new smallest = 5.205i = 8 new smallest = 4.783i = 19 new smallest = 4.774i = 21 new smallest = 4.683i = 99 new smallest = 4.666i = 300 new smallest = 4.625i = 324 new smallest = 4.238i = 603 new smallest = 4.186i = 627 new smallest = 4.174i = 2244 new smallest = 4.128i = 2256 new smallest = 3.746i = 2262 new smallest = 3.734i = 4114 new smallest = 3.495i = 7284 new smallest = 3.326i = 9520 new smallest = 3.274i = 9640 new smallest = 3.262i = 74468 new smallest = 3.226i = 139466 new smallest = 3.185i = 139476 new smallest = 2.952i = 140647 new smallest = 2.943i = 179796 new smallest = 2.842i = 273364 new smallest = 2.778i = 480496 new smallest = 2.776i = 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.

 `min2 8 7 0 5 4 9 3 1 6 2.69758.8522 sec2 8 7 0 5 4 9 3 1 6 2.69744.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 retvaldef 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()`