Branch & bound (english)

The Branch and Bound algorithm is an intelligent enumeration of the tree of possible solutions.

As the name suggests, the algorithm has two steps:

  1. separation: separating a set of solutions into subsets;
  2. 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 three-variable problem, the full tree of separation in ascending order of the variables is as follows:

b&b

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.

For subsets of solutions to be tested, noted Si, we are looking for a lower bound of the objective function in each subset. So we have evaluation(Si)≤min(x∈Si) f(x). For the case of a maximum, we are looking for an upper bound evaluation evaluation(Si)≥max(x∈Si) f(x).

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(Si)≥z, then Si contains no optimal solution, it is not useful to explore in detail the subset Si.
    • If evaluation(Si)<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*xA+8*xB+13*xC+17*xD+20*xE sous 2*xA+3*xB+4*xC+5*xD+7*xE≤18 with xi 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. xD being the largest, we will perform the separation on this criterion. We will get 4 branches for respectively xD=3, 2, 1 et 0 :

  • xD=3. We solve the relaxed linear program which gives xC=3/4 and z=60.75. This is an inadmissible solution thus separated over xA :
    • xA=1. The relaxed linear problem gives xC=1/4 and z=60.25. This is an inadmissible solution. It is no longer possible to separate because there is no longer xi>0. The closest whole solution comes back to our original solution.
    • xA=0. The relaxed linear problem gives xB=1. The solution is admissible and is equal to z=59. z is updated.
  • xD=2. The relaxed linear problem gives xC=2 and z=60. The solution is admissible. z is updated.
  • xD=1. The relaxed linear problem gives xC=13/4 and z=59,25. This bound is less than z, so we do not visit this branch.
  • xD=0. The relaxed linear problem gives xC=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).

b&b2

Publicités