This example uses an algorithm to find a number's prime factors. For other interesting algorithms, see my book Essential Algorithms, Second Edition. The book describes many fascinating algorithms in pseudocode with source code available for download in Python and C#.

Title: Use branch and bound to solve the traveling salesman problem in Python

[A solution to the traveling salesman problem found by branch and bound] The post Use random search to solve the traveling salesman problem in Python explains how you can use a random search to find solutions to the traveling salesman problem (TSP). Unfortunately, the number of possible tours in the TSP problem grows extremely quickly as the number of points increases so it's unlikely that a random search will find the best possible solution unless the number of points if very small.

The post Use exhaustive search to solve the traveling salesman problem in Python explains how you can exhaustively examine every possible tour to find the shortest one. Unfortunately, it takes a long time to examine the huge number of possible tours so you can only use exhaustive search for relatively small TSP problems. In one set of tests, exhaustive search took 11.78 seconds to examine all tours containing 10 points, 2 minutes 39 seconds to examine all tours containing 11 points, and more than 35 minutes to examine all tours containing 12 points. You might have the patience to examine slightly larger problems, but you'll quickly reach the limit of your patience (or lifetime for larger problems).

Branch and bound is a technique that lets you skip some of the possible tours so it saves you time. One drawback to branch and bound is that the amount of time saved depends on the precise arrangement of the points, so the results vary from problem to problem. Branch and bound is always faster than an exhaustive search, it's just not clear how much faster until you try it.

Branch and Bound

The idea behind branch and bound is to start examining all possible tours as in an exhaustive search. As the search progresses, you keep track of the best solution found so far. When you're about to add a new point to the current tour, you ask, "What is the shortest possible tour we can get if we add this point now?" If the shortest possible tour is no shorter than the current best tour, then we skip adding that point.

That not only lets you skip adding that point, but it lets you avoid checking any tour that begins with the current tour followed by the new point. If the current tour is short, that can let you skip a huge fraction of all of the possible tours.

One trick is figuring out how short a new tour might be. You can't do that exactly, but you can get a lower bound on the length. For example, suppose the current tour has length L and we still need to add point A, B, and C to the tour. One way to get a lower bound for the total tour length is to add the smallest distances leading to points A, B, and C to L. For example, suppose L_A is the smallest distances from any point to point A. Then when we add point A to the tour, the tour's length will increase by at least L_A.

That's the way we estimate the tour's final length. We loop through all of the points that are not currently in the tour, find the shortest distance into those points, and add those distances to the tour's current length. If the best solution found so far has a shorter length then the current partial tour, then we know that the current tour cannot be shorter so we can stop building it.

Code

The following make_b_and_b_tour_generator method generates all possible tours.

def make_b_and_b_tour_generator(num_points, distances, **_): '''Use branch and bound to find tours.''' global num_calls num_calls = 0 # Prepare to call generate_b_and_b_tours. is_used = [False for i in range(num_points)] # Arbitrarily start at point 0. is_used[0] = True current_tour = [0] current_length = 0 # Solve recursively. best_length = math.inf for length, tour in generate_b_and_b_tours( num_points, distances, is_used, current_tour, current_length, best_length): yield length, tour

This code initializes global variable num_calls to zero. It then creates the is_used list to keep track of the points in the current tour. It arbitrarily puts the first point in the tour and then recursively calls the generate_b_and_b_tours method to generate all of the tours. That method is a generator, so this method must iterate through its results and re-yield them.

The following code shows the generate_b_and_b_tours method.

def generate_b_and_b_tours(num_points, distances, is_used, current_tour, current_length, best_length): '''Generate all possible tours.''' global num_calls num_calls += 1 # See if we have a full tour. if len(current_tour) == num_points: # We have a full tour. # Add the distance from the last point back to the first. current_length += distances[current_tour[-1]][current_tour[0]] # Yield it. yield current_length, current_tour else: # Pick the next point to add to the tour. for i in range(num_points): # Try to add points[i]. if not is_used[i]: # Get the distance needed to add point i to the tour. distance_to_i = distances[current_tour[-1]][i] current_length += distance_to_i # Add it. is_used[i] = True current_tour.append(i) # Calculate the best possible tour length from here. test_length = current_length + \ best_possible_length(num_points, distances, is_used) if test_length < best_length: # Recursively complete the tour. # Repeat until the nested generator runs dry. for length, tour in generate_b_and_b_tours( num_points, distances, is_used, current_tour, current_length, best_length): # Update the best tour length. if length < best_length: best_length = length # Yield the tour. yield length, tour # Remove points[i] so we can use it again later. current_length -= distance_to_i is_used[i] = False current_tour.pop()

This method inrcements num_calls. It then checks the current tour's length to see if we have a complete tour. If so, the code adds the distance from the tour's final point to its beginning (to close the tour) and yields the result.

If we don't have a complete tour, the code loops through all of the possible points that it could add to the tour next. For each such point, the code adds the distance from the tour's last point to the new point to the tour's total length. It also adds the new point to the tour.

Next, the code calls the best_possible_length function described shortly to find the sum of the best possible lengths needed to add the remaining points to the tour. If that value plus the tour's current length is less than the best tour length found so far, the method calls itself recursively to explore the extended tour. The recursive call is a generator, so the method must loop through its results and re-yield them.

As if works through the returned results, the code updates best_length so future calls can use the new best length in the bounds test.

After it finishes processing the returned results, the code removes the new point from the tour and moves on to consider other points that it could add to the tour at this point.

The following code shows the best_possible_length function.

def best_possible_length(num_points, distances, is_used): '''Return the best possible tour length starting from the current tour.''' # Loop through the points. total_length = 0 for i in range(num_points): # If point i is unused... if not is_used[i]: # ...find smallest distance into point i. length_to_i = math.inf for j in range(num_points): if j != i and distances[j][i] < length_to_i: length_to_i = distances[j][i] total_length += length_to_i return total_length

This code loops through the points. If a point is not in the current tour (like point A in the earlier example), it loops through the points again, finds the shortest distance to point A, and adds that distance to total_length. After it finishes adding the distances to all of the points, the function returns the total distance.

Summary

Finding the best possible solution to the TSP can be difficult because there are so many possible solutions. Exhaustive search only works for small problems and random search doesn't guarantee the best possible solution. (In fact, for large problems, random search is practically guarantees to not give you the best possible solution.)

Branch and bound lets you perform an exhaustive search while skipping huge parts of the solution space so you can solve larger problems exactly.

Here's a table showing times and the number of function calls used by exhaustive search and branch and bound in one set of tests.

# Points	Exhaustive Calls	B & B Calls	Exhaustive Time (sec)	B & B Time (sec)
8	13,700	2,616	0.14	0.01
9	109,601	4,238	1.21	0.02
10	986,410	16,594	12.56	0.08
11	9,864,101	108,224	159.32	0.53
12	108,505,112	157,284	2,103.36	1.25
13	---	95,320	---	1.11
14	---	525,007	---	9.43
15	---	2,691,197	---	61.85

You can see that branch and bound makes far fewer recursive function calls so it takes much less time. The exact number of solutions examined (and thus time) by branch and bound depends on the arrangement of points, so those values are not consistent. The 13-point test, for example, used fewer function calls than the 11- and 12-point tests and took less time than the 12-point test. Still, branch and bound is always faster than an exhaustive search and always produces an optimal tour.

Download the example and see the two previous posts to experiment and to see additional details.