Branching and Bounding

Branch and Bound algorithms produce some number of possible new branches, from some starting point. On these branches, a cost function (called $f(s)$) representing the current cost of the solution, plus some penalty for not having finished the task yet is defined. Furthermore, we define a lower-bound (called $g(s)$) on the cost, which is used for bounding our search.

When we have some number of possible new branches to search thru, we can ignore all branches having a $g(s) \leq f(\mathrm{best})$, and their entire sub-trees.

If the $g(s)$ function is close to the true cost of completing the search along some branch, we will be able to cut away most of the unnecessary branches. If the function is not very close, however, we will still have to search thru some very large domain.

Often the quality of $g(s)$ and the time it takes to compute is a compromise, and one will have to experiment to find a viable routine. However, if the quality of $g(s)$ is low, nothing else in the search algorithm will be able to compensate for this.