Going for hiking and having difficulty packing your rucksack? Optimizaton and Search: The branch and bound algorithm

A branch and bound is an algorithm paradigm. It basically relies on a combinatorial approach and is hence used for combinatorial optimization like the knapsack problem.

Have you ever watered and maintained your garden? Going around removing weeds around trees and removing unwanted branches growing from your plants to keep them in the best possible symmetry, so that your neighbor envies your garden for the perfect shape it's always in. Removing over-ripe fruits so that they don't spoil the other around them. Cutting and pruning at each step so that you don't have to deal with a huge jungle later on.

Well, this is the basic principle for B&B. Below is a more detailed explanation.

It usually of the form of a decision tree where each decision is represented by an edge. The leaves of this tree is the set of all possible solutions. To find the most optimized solution(i.e. one of the leaves) the following is the basis of evaluation.

The intuition is that you start from the root and calculate an upper bound if the problem asks the function to be maximized (or lower bound for function minimization in case of TSP where distance is to be minimized) for a function you want to optimize. This bound describes the best you can get from the sub-tree below the node. It is to be kept in mind that this bound is re-calculated every time a decision is made in the tree. This bound describes the most optimistic solution you can find in one of the leaves of the sub-tree rooted at this particular node.

Make a series of decisions and find the first solution. Now this is your benchmark. Compare this solution obtained with the optimized evaluation of the function at each level (i.e. after every decision). As the root of a sub-tree bounds the best you can achieve from any of the leaves of that sub-tree; if the root of the sub-tree in question has a higher optimized evaluation then you can search that sub-tree in hope for a better solution you already have else discard the whole sub-tree below (called pruning).

If a better solution is found it's updated as the benchmark.

Keep searching the main tree for solutions better than what you have (benchmark) and prune the sub-trees which have a lower optimized evaluation than the benchmark.

Pruning reduces the search space by an amount depending on where the pruning of the tree occurs. Generally, it helps in reducing it by a large factor.

The above is an instance of the knapsack (max weight is 16) using Branch and Bound. The weight and the value of the item is enlisted on the left.

Each node has current value, space occupied and optimistic evaluation of the value of its sub-tree. 

1. The root shows that currently no items have been selected and the best one can do is 115$.(or less)

2. A decision is made to accept the Item 1.

3. If Item 1 is accepted then we go to left of root else right of root.

4. Going left the value of the knapsack is increased and the weight is also updated. An optimistic evaluation is calculated for the results under this node.(i.e. all possible ways of selecting remaining items after selecting Item 1)

5. Going right the value of the knapsack and the weight is unchanged (since nothing was chosen). An optimistic evaluation is calculated for the results under this node.(i.e. results with all possible ways of selecting remaining items after discarding Item 1)

6. If a node has optimistic evaluation less than the best we have found then the sub-tree is discarded. If a node occurs such that the weight surpasses the max allowed weight by the knapsack then again the sub-tree under the node is discarded.

The first solution is found and set as the benchmark and the above steps are repeated until the whole search space has been exhausted.

This is the basic idea of Branch and Bound.