What is a branch and bound algorithm design?

Many problems include several possible scenarios, and we need to find the optimal one. The branch and bound algorithm comes in handy where combinatorial optimization is required. Typically, these problems require all possible permutations in the worst-case scenario. Branch and bound algorithm create branches and bound to the best solution.

Let’s start with the root node and bound our solution to the left node, excluding the right subtree from our search.

Example

Let’s see the solution to the knapsack problem using the branch and bound approach. Here we have five items, and the profit and weight for each item are mentioned in the table.

The knapsack has a capacity of a total weight 15:

Conclusion

Our goal is to maximize the profit while the total weight does not exceed 15. The nodes in gray color are ignored because they either do not produce a maximum profit or the best solution by them will be worst than the current solution. The nodes in red exceed the weight limit So, we can ignore them. The green node gives the maximum profit of 42.