Branch and Bound Algorithms

Backtracking is to cut off a branch of the problem‘s state-space tree as soon as we can deduce that it cannot lead to a solution.This idea can be strengthened further if we deal with an optimization problem, one that seeks to minimize or maximize an objective function, usually subject to some constraints.Note that in the standard terminology of optimization problems, a feasible solution is a point in the problem‘s search space that satisfies all the problem‘s constraints (e.g. a Hamiltonian circuit in the traveling salesman problem, a subset of items whose total weight does not exceed the knapsack‘s capacity),while an optimal solution is a feasible solution with the best value of the objective function (e.g., the shortest Hamiltonian circuit, the most valuable subset of items that fit the
knapsack).


Compared to backtracking, branch-and-bound requires two additional items.A way to provide, for every node of a state-space tree, a bound on the best value of the objective functions on any solution that can be obtained by adding further components to the partial solution represented by the node .


GENERAL METHOD


If this information is available, we can compare a node‘s bound value with the value of the best solution seen so far:
if the bound value is not better than the best solution seen so far—i.e., not smaller for a minimization problem and not larger for a maximization problem—the node is nonpromising and can be terminated (some people say the branch is pruned) because no solution obtained from it can yield a better solution than the one already available.


E.g. Termination of search path
In general, we terminate a search path at the current node in a state-space tree of a branch-and-bound algorithm for any one of the following three reasons:
1. The value of the node‘s bound is not better than the value of the best solution seen so far.
2. The node represents no feasible solutions because the constraints of the problem are already violated.
3. The subset of feasible solutions represented by the node consists of a single point (and hence no further choices can be made)—in this case we compare the value of the objective function for this feasible solution with that of the best solution seen so far and update the latter with the former if the new solution is better.