Trusted answers to developer questions
Trusted Answers to Developer Questions

Related Tags

algorithm

What is a branch and bound algorithm design?

Ayyaz Sheikh

Grokking Modern System Design Interview for Engineers & Managers

Ace your System Design Interview and take your career to the next level. Learn to handle the design of applications like Netflix, Quora, Facebook, Uber, and many more in a 45-min interview. Learn the RESHADED framework for architecting web-scale applications by determining requirements, constraints, and assumptions before diving into a step-by-step design process.

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.

%0 node_1 node_2 node_1->node_2 node_3 X node_1->node_3 node_1631168384831 node_2->node_1631168384831 node_1631168389903 X node_2->node_1631168389903 node_1631168424670 X node_3->node_1631168424670 node_1631168424987 X node_3->node_1631168424987

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:

Items To Pick

Items

Profit

Weight

0

0

0

1

11

2

2

21

5

3

31

13

4

33

10

5

43

33

Initial stage when there is no item
1 of 4

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.

RELATED TAGS

algorithm

CONTRIBUTOR

Ayyaz Sheikh
Copyright ©2022 Educative, Inc. All rights reserved

Grokking Modern System Design Interview for Engineers & Managers

Ace your System Design Interview and take your career to the next level. Learn to handle the design of applications like Netflix, Quora, Facebook, Uber, and many more in a 45-min interview. Learn the RESHADED framework for architecting web-scale applications by determining requirements, constraints, and assumptions before diving into a step-by-step design process.

Keep Exploring