Branch and bound

Branch and bound

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

As its name suggests, the algorithm has two times:

  1. separation: to separate a set of solutions into subsets;
  2. evaluation: evaluate the solutions of a subset by increasing the value of the best solution of this subset.

The Branch and bound algorithm (Separation and evaluation) proposes to go through the tree structure 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 deems useless to explore it directly after.

The Branch and bound algorithm is often used in place of dynamic programming. The evaluation is often the objective function with relaxed constraints (by decreasing number) according to the depth.

The separation

Branch and bound begins with separation. The set of solutions is separated by fixing the value of one or more variables of the problem. Suppose a problem with three variables, the complete tree of separation in ascending order of the variables is as follows:

branch and bound séparation

There are two exploration techniques, linked to the paths of a tree. The breadth first consists in favoring the widening of possibilities by increasing depth, there is no backtracking. The depth first favors the widening of possibilities by visiting the deepest leaves. The advantage is to quickly deliver "good" solutions and to eliminate sub-optimal branches.

Evaluation

Branch and bound takes turns evaluating each separation. The root of the tree is an admissible solution which will serve as a reference. We thus obtain a solution giving a value z increasing the optimal solution.

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

Assessment is often performed on the initial problem after relaxation. A relaxation makes it possible to pass from complex constraints to linear constraints or of which the dual is simple. For example, integrity relaxation allows working with real variables instead of whole variables.

Once the assessment has been carried out, two cases are possible:

  • If evaluation (Si) ≥z, then Si does not contain any optimal solution, it is not useful to explore in detail the subset Si.
  • If evaluation (Si) <z, alors on teste l’admissibilité de la solution d’évaluation. Si elle est admissible, on actualise z, sinon on continue l’exploration jusqu’à l’obtention d’une des conditions précédentes.

Example: backpack problem

A cargo plane has a cargo capacity of 18 volume units. He must transport containers of goods in such a way as to maximize the total value of his cargo. The available containers are in unlimited quantity for each type:

  • Type A container, value 6, volume 2;
  • Type B container, value 8, volume 3;
  • Type C container, value 13, volume 4;
  • Type D container, value 17, volume 5;
  • Type E container, value 20, volume 7.

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 * xTO+ 8 * xB+ 13 * xVS+ 17 * xD+ 20 * xE under 2 * xTO+ 3 * xB+ 4 * xVS+ 5 * xD+ 7 * xE≤18 with xi the integer number of type i containers.

The initial solution is carried out by the greedy algorithm of the best value / volume ratio. We get 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 obtain 4 branches for respectively xD= 3, 2, 1 and 0:

  • xD= 3. We solve the relaxed linear program which gives xVS= 3/4 and z = 60.75. It is an inadmissible solution therefore one separates compared to xTO :
    • xTO= 1. The relaxed linear problem gives xVS= 1/4 and z = 60.25. This is an unacceptable solution. It is no longer possible to separate because there are no more xi> 0. The closest whole solution comes down to our starting approximate solution.
    • xTO= 0. The relaxed linear problem gives xB= 1. The solution is admissible and gives z = 59. We update z.
  • xD= 2. We solve the relaxed linear program which gives xVS= 2 and z = 60. It is an admissible solution so we update z.
  • xD= 1. We solve the relaxed linear program which gives xVS= 13/4 and z = 59.25. This bound is lower than z, so we do not visit this branch.
  • xD= 0. We solve the relaxed linear program which gives xVS= 9/2 and z = 58.5. This bound is lower than z, so we do not visit this branch.

The whole area is explored. The optimum z * = 60 was obtained with the solution vector (0,0,2,2,0).

branch and bound sac-à-dos

To share
en_GBEN
%d bloggers like this: