0-1 Knapsack problem using Branch and Bound

In this article, we have explored the Branch and Bound algorithm for 0-1 Knapsack problem.

Contents

1. Problem Statement
2. Approaches to Solve this Method
3. Branch and Bound Method
4. Time and Space Complexity
5. Solving an Example
6. Conclusion

Problem Statement

We are a given a set of n objects which have each have a value v_i and a weight w_i. The objective of the 0/1 Knapsack problem is to find a subset of objects such that the total value is maximized, and the sum of weights of the objects does not exceed a given threshold W. An important condition here is that one can either take the entire object or leave it. It is not possible to take a fraction of the object.

Consider an example where n = 4, and the values are given by {10, 12, 12, 18}and the weights given by {2, 4, 6, 9}. The maximum weight is given by W = 15. Here, the solution to the problem will be including the first, third and the fourth objects.

Approaches to solve this problem

The first idea that comes to mind as soon as we look at the problem would be to look at all possible combinations of objects, calculate their total weight, and if the total weight is less than the threshold, to calculate the total value (This approach is known as the Brute Force. Although this approach would give us the solution, it is of exponential time complexity. Hence, we look at the other possible methods.

We can use the Dynamic Programming approach to solve this problem as well. Although this method is far more efficient than the Brute Force method, it does not work in scenarios where the item weights are non-integer values.

Backtracking can also be used to solve this problem. However, this would mean exploring all possible branches until the solution is invalid, then going back a step and exploring other possibilities. As was in the case of the brute force method, this method also has exponential time complexity.

Since this is a combinatorial problem, once can use the Branch and Bound method to solve this problem. We shall explore this way of solving this problem in detail.

Branch and Bound Method

In solving this problem, we shall use the Least Cost- Branch and Bound method, since this shall help us eliminate exploring certain branches of the tree. We shall also be using the fixed-size solution here. Another thing to be noted here is that this problem is a maximization problem, whereas the Branch and Bound method is for minimization problems. Hence, the values will be multiplied by -1 so that this problem gets converted into a minimization problem.

Now, consider the 0/1 knapsack problem with n objects and total weight W. We define the upper bound(U) to be the summation of v_ix_i (where v_i denotes the value of that objects, and x_i is a binary value, which indicates whether the object is to be included or not), such that the total weights of the included objects is less than W. The initial value of U is calculated at the initial position, where objects are added in order until the initial position is filled.

We define the cost function to be the summation of v_if_i, such that the total value is the maximum that can be obtained which is less than or equal to W. Here f_i indicates the fraction of the object that is to be included. Although we use fractions here, it is not included in the final solution.

Here, the procedure to solve the problem is as follows are:

• Calculate the cost function and the Upper bound for the two children of each node. Here, the (i + 1)^th level indicates whether the i^th object is to be included or not.
• If the cost function for a given node is greater than the upper bound, then the node need not be explored further. Hence, we can kill this node. Otherwise, calculate the upper bound for this node. If this value is less than U, then replace the value of U with this value. Then, kill all unexplored nodes which have cost function greater than this value.
• The next node to be checked after reaching all nodes in a particular level will be the one with the least cost function value among the unexplored nodes.
• While including an object, one needs to check whether the adding the object crossed the threshold. If it does, one has reached the terminal point in that branch, and all the succeeding objects will not be included.

In this manner, we shall find a value of U at the end which eliminates all other possibilites. The path to this node will determine the solution to this problem.

Time and Space Complexity

Even though this method is more efficient than the other solutions to this problem, its worst case time complexity is still given by O(2ⁿ), in cases where the entire tree has to be explored. However, in its best case, only one path through the tree will have to explored, and hence its best case time complexity is given by O(n). Since this method requires the creation of the state space tree, itsspace complexity will also be exponential.

Solving an Example

Consider the problem with n =4, V = {10, 10, 12, 18}, w = {2, 4, 6, 9} and W = 15. Here, we calculate the initital upper bound to be U = 10 + 10 + 12 = 32. Note that the 4th object cannot be included here, since that would exceed W. For the cost, we add 3/9 ^th of the final value, and hence the cost function is 38. Remember to negate the values after calculation before comparison.

After calculating the cost at each node, kill nodes that do not need exploring. Hence, the final state space tree will be as follows (Here, the number of the node denotes the order in which the state space tree was explored):

Note here that node 3 and node 5 have been killed after updating U at node 7. Also, node 6 is not explored further, since adding any more weight exceeds the threshold. At the end, only nodes 6 and 8 remain. Since the value of U is less for node 8, we select this node. Hence the solution is {1, 1, 0, 1}, and we can see here that the total weight is exactly equal to the threshold value in this case.

Conclusion

We can see that the branch and bound method will give the solution to the problem by exploring just 1 path in the best case. Although the worst case will be of exponential time complexity, this method will perform better than the other methods in most scenarios, since multiple branches get eliminated in each iteration.

With this article at OpenGenus, you must have the complete idea of solving 0-1 Knapsack problem using Branch and Bound.