Branch and bound
From DDL Wiki
Branch and bound refers to a class of implicit enumeration techniques that are used to solve optimization problems.
One way to view branch and bound is as a tree (a tree in the graph theory sense, not a plant). Suppose that we wish to minimize f(x) over 
. The root of the tree is the set S of all feasible solutions. Each node n in the tree is a subset Sn of S, and the branches of node n correspond to disjoint subsets of the subset Sn. Starting from the root, branch and bound techniques iteratively generate branches for the tree. At each level, the subsets become smaller and smaller and eventually the nodes become individual feasible solutions. If we generated all of the possible branches and nodes, then we would exhaustively search the set of all feasible solutions.
However, this is not necessary. We associate with each node n a lower bound LBn such that 
for all 
. Now, let f * be the optimal value of f(x). We can get upper bounds on f * by evaluating any feasible solution. If we know that LBn > f * , we know that no solution in the subset Sn can be optimal. Thus, further exploring the branches of this node is pointless.
Branch and bound techniques differ in the way that they generate new branches and decide which node to explore next. Also, there may be multiple techniques for finding a lower bound.
Branch and bound techniques have been applied to many different types of problems. In the area of sequencing and machine scheduling, an important early reference is Lenstra (1977)
References
Lenstra, J.K., Sequencing by Enumerative Methods, Mathematisch Centrum, Amsterdam, 1977.
