Least cost branch and bound
Branch and bound is an algorithm to find the optimal solution to various optimization problems. It is very similar to the backtracking strategy, only just in the backtracking method state-space tree is used. The benefit of the branch and bound method is that it does not limit us to only a certain way of traversing the tree. Though it also has certain drawbacks, one being it is much slower and gets an exponential time complexity in the worst cases. The branch and bound method are applicable to many discrete combinational problems.
The branch and bound can be solved using FIFO, LIFO, and least count strategies. The selection rule used in the FIFO or LIFO linked list can sometimes be erroneous, as it does not give preference to certain nodes, and hence may not find the best response as quickly. To overcome this drawback we use the least cost method, which is also considered to be an intelligent method as it uses an intelligent ranking method. It is also referred to as the approximate cost function “C”.
The least-cost method of branch and bound selects the next node based on the Heuristic Cost Function, and it picks the one with the least count, therefore it is one of the best methods. In the 0/1 knapsack problem, we need to maximize the total value, but we cannot directly use the least count branch and bound method to solve this.
Therefore, we convert this into a minimization problem by taking the negative of the given values.
The steps to solve the 0/1 Knapsack problem is as follows:
- We need to sort the items based on the value/ weight ratio.
- A dummy node is inserted in the priority queue.
- Then we follow the following steps until the priority queue is empty:
- The peak element from the priority queue is extracted and inserted into the current node.
- When the upper bound of the current node is less than the minimum lower bound then we proceed further with the next element.
- We do not consider the elements with upper bounds more than the minimum lower bound as the upper bound stores the best value, and if the best value is itself not optimal than the minimum lower bound then exploring further is of no use.
- Then update the path array.
- We check the node level of the current node, if the lower node level of the current node is less than the final lower bound then we update the final path and final lower bound. If it is not less than the final lower bound then we continue with the next element.
- The lower and upper bounds of the right child of the current node are calculated.
- Then we calculate the lower and upper bounds of the left child of the current node if the current item can be inserted in a knapsack.
- We finally update the minimum lower bound and insert the children, in case the upper bound is less than the minimum lower bound.
Reference