The Branch and Bound algorithm is an intelligent enumeration of the tree of possible solutions.
As the name suggests, the algorithm has two steps:
 separation: separating a set of solutions into subsets;
 evaluation: evaluating the solutions of a subset by increasing the value of the best solution of this subset.
The algorithm proposes to browse the tree of possible solutions by evaluating each subset of solutions. It keeps in memory the value of the best solution f(s) found so far. When the evaluation of a subset gives a value lower than f(s), the algorithm finds it useless to explore it.
The branch and bound algorithm is often used instead of dynamic programming. Evaluation is often the objective function with constraints relaxed (by decreasing number) depending on the depth.
Separation
The set of solutions is separated by setting the value of one or more variables of the problem. Suppose a threevariable problem, the full tree of separation in ascending order of the variables is as follows:
There are two exploration techniques, related to the path of a tree. The width first is to promote the widening of opportunities by increasing depth, there is no backtracking. Depth first favors the widening of possibilities by visiting the deepest leaves. The advantage is to quickly provide « good » solutions and eliminate suboptimal branches.
Evaluation
The root of the tree is an acceptable solution that will serve as a reference. So we get a solution giving a value z as an upper bound the optimal solution.
Evaluation is often carried out on the initial problem after relaxation. A relaxation toggles complex constraints to linear or whose dual is simple constraints. For example, an integrity relaxation allows you to work with real variables instead of integer variables.
Once the evaluation has been completed, two cases are possible (for a min):

 If evaluation(S_{i})≥z, then S_{i} contains no optimal solution, it is not useful to explore in detail the subset S_{i}.
 If evaluation(S_{i})<z, then we test the eligibility of the evaluation solution. If it is admissible, we update z, otherwise we continue the exploration until one of the preceding conditions is obtained.
Example: knapsack problem
A cargo plane has a cargo capacity of 18 volume units. He must carry freight containers in order to maximize the total value of his cargo. The available containers are in unlimited quantity for each type:
 Container A, value 6, volume 2;
 Container B, value 8, volume 3;
 Container C, value 13, volume 4;
 Container D, value 17, volume 5;
 Container E, value 20, volume 7.
At first, we will solve the problem using a greedy algorithm. Then we will determine the optimal solution by a Branch & Bound procedure.
The mathematical modeling of the problem is the following system: max z=6*x_{A}+8*x_{B}+13*x_{C}+17*x_{D}+20*x_{E} sous 2*x_{A}+3*x_{B}+4*x_{C}+5*x_{D}+7*x_{E}≤18 with x_{i} the number of container of type i.
The initial solution is realized by the greedy algorithm of the best ratio value / volume. We obtain the solution vector (1,0,0,3,0) with z=57. x_{D} being the largest, we will perform the separation on this criterion. We will get 4 branches for respectively x_{D}=3, 2, 1 et 0 :
 x_{D}=3. We solve the relaxed linear program which gives x_{C}=3/4 and z=60.75. This is an inadmissible solution thus separated over x_{A} :
 x_{A}=1. The relaxed linear problem gives x_{C}=1/4 and z=60.25. This is an inadmissible solution. It is no longer possible to separate because there is no longer x_{i}>0. The closest whole solution comes back to our original solution.
 x_{A}=0. The relaxed linear problem gives x_{B}=1. The solution is admissible and is equal to z=59. z is updated.
 x_{D}=2. The relaxed linear problem gives x_{C}=2 and z=60. The solution is admissible. z is updated.
 x_{D}=1. The relaxed linear problem gives x_{C}=13/4 and z=59,25. This bound is less than z, so we do not visit this branch.
 x_{D}=0. The relaxed linear problem gives x_{C}=9/2 and z=58,5. This bound is less than z, so we do not visit this branch.
The whole domain is explored. The optimum z*=60 was obtained with the solution vector (0,0,2,2,0).