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 =  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()