Knapsack Problem (Branch and Bound approach):

Here’s my bag. Let’s get maximum profit!!

Knapsack Problem:

Given two arrays v[] and w[] that represent values and weights associated with n items respectively. Find out the maximum value subset(Maximum Profit) of v[] such that sum of the weights of this subset is smaller than or equal to Knapsack capacity Cap(W).

Branch and bound (BB) is an algorithm design paradigm for discrete and combinatorial optimization problems, as well as mathematical optimization.

Combinatorial optimization problems are mostly exponential in terms of time complexity.

Also it may require to solve all possible permutations of the problem in worst case.

So, by using Branch and Bound it can be solved quickly.

Other Methods to solve Knapsack problem:

1. Greedy Approach: It gives optimal solution if we are talking about fraction Knapsack. (By taking items according to V/W ratio). For 0/1 Knapsack it may or may not give optimal solution.
2. Dynamic Approach: In this approach, we use a 2D table of size n x W(capacity). It doesn’t work if the capacity is not integer.
3. Brute Force: With n items, there are 2^n solutions to be generated, check each to see if they satisfy the constraint, save maximum solution that satisfies constraint. This solution can be expressed as tree.

There are two options take(in) or do not take(out).So for each item there will be two possibilities.

And at last take the most optimal solution from the lowest level.

4. Backtracking: Use Backtracking to optimize the Brute Force solution. If we reach a point where a solution no longer is feasible, there is no need to continue exploring. In the given example, backtracking would be much more effective if we had even more items or a smaller knapsack capacity.

5.Branch and Bound :

The backtracking based solution works better than brute force by ignoring infeasible solutions. To do better (than backtracking) 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.

To find bound for every node for Knapsack:

To check if a particular node can give us a better solution or not, we compute the optimal solution (through the node) using Greedy method. If the solution computed by Greedy approach is more than the best until now , then we can’t get a better solution through the node.

Algorithm:

1. Sort all items in decreasing order of V/W so that upper bound can be computed using Greedy Approach.(The nodes taken in the image are accordingly.)
2. Initialize profit, max = 0
3. Create an empty queue, Q.
4. Create a dummy node of decision tree and enqueue it to Q. Profit and weight of dummy node are 0.
5. Do while (Q is not empty).

• Extract an item from Q. Let the item be x.
• Compute profit of next level node. If the profit is more than max, then update max. (Profit from root to this node (include this node)).
• Compute bound of next level node. If bound is more than max, then add next level node to Q.(Upper Bound of the maximum Profit in subtree of this node)
• Consider the case when next level node is not considered as part of solution and add a node to queue with level as next, but weight and profit without considering next level nodes.

Branch and bound is very useful technique for searching a solution but in worst case, we need to fully calculate the entire tree. At best, we only need to fully calculate one path through the tree and prune the rest of it.

References:

Branch and bound

Branch and Bound Algorithm - GeeksforGeeks