Branch and Bound Algorithm

DSA for Beginners
Learn more about Branch and Bound in DSA Self Paced Course

Branch and bound is an algorithm design paradigm which is generally used for solving combinatorial optimization problems. These problems are typically exponential in terms of time complexity and may require exploring all possible permutations in worst case. The Branch and Bound Algorithm technique solves these problems relatively quickly.

Let us consider the 0/1 Knapsack problem to understand Branch and Bound.

There are many algorithms by which the knapsack problem can be solved:

• DP solution for 0/1 Knapsack
• Backtracking Solution for 0/1 Knapsack.

Let’s see the Branch and Bound Approach to solve the 0/1 Knapsack problem: The Backtracking Solution can be optimized if we know a bound on best possible solution subtree rooted with every node. If the best in subtree is worse than current best, we can simply ignore this node and its subtrees. So we compute bound (best solution) for every node and compare the bound with current best solution before exploring the node.

Example bounds used in below diagram are, A down can give $315, B down can $275, C down can $225, D down can $125 and E down can $30.

1. Branch and Bound | Set 1 (Introduction with 0/1 Knapsack)
2. Branch and Bound | Set 2 (Implementation of 0/1 Knapsack)
3. Branch and Bound | Set 3 (8 puzzle Problem)
4. Branch And Bound | Set 4 (Job Assignment Problem)
5. Branch and Bound | Set 5 (N Queen Problem)
6. Branch And Bound | Set 6 (Traveling Salesman Problem)

• Learn Data Structure and Algorithms | DSA Tutorial

If you like GeeksforGeeks and would like to contribute, you can also write an article and mail your article to review-team@geeksforgeeks.org. See your article appearing on the GeeksforGeeks main page and help other Geeks.

Please write comments if you find anything incorrect, or if you want to share more information about the topic discussed above