Branch and bound

Contenus

L’algorithme de Branch and bound (Séparation et évaluation) est une énumération « intelligente » de l’arbre des solutions possibles.

Comme son nom l’indique, l’algorithme possède deux temps :

la séparation : séparer un ensemble de solutions en sous-ensembles;
l’évaluation : évaluer les solutions d’un sous-ensemble en majorant la valeur de la meilleure solution de ce sous-ensemble.

L’algorithme de Branch and bound (Séparation et évaluation) propose de parcourir l’arborescence des solutions possibles en évaluant chaque sous-ensemble de solutions. Il garde en mémoire la valeur de la meilleure solution f(s) trouvée jusqu’à présent. Quand l’évaluation d’un sous-ensemble donne une valeur plus faible que f(s), l’algorithme juge inutile de l’explorer directement après.

L’algorithme de Branch and bound (Séparation et évaluation) est souvent utilisé à la place de la programmation dynamique. L’évaluation est souvent la fonction objectif avec des contraintes relaxés (par nombre décroissant) en fonction de la profondeur.

La séparation

Branch and bound (Séparation et évaluation) commence par la séparation. L’ensemble des solutions est séparé en fixant la valeur d’une ou de plusieurs variables du problème. Supposons un problème à trois variables, l’arbre complet de séparation par ordre croissant des variables est le suivant :

Il existe deux techniques d’exploration, lié aux parcours d’un arbre. La largeur d’abord consiste à favoriser l’élargissement des possibilités par profondeur croissante, il n’y a pas de backtracking. La profondeur d’abord favorise l’élargissement des possibilités par visite des feuilles les plus profondes. L’avantage est de fournir rapidement des « bonnes » solutions et d’éliminer des branches sous-optimales.

L’évaluation

Branch and bound (Séparation et évaluation) évalue à tour de rôle chaque séparation. La racine de l’arbre est une solution admissible qui servira de référence. Nous obtenons donc une solution donnant une valeur z majorant la solution optimale.

Pour les sous-ensembles de solutions à tester, noté S_i, nous recherchons un minorant de la fonction objectif dans chaque sous-ensemble. Nous avons donc evaluation(S_i)≤min_{(x∈S_i)} f(x). Pour le cas d’un maximum, nous recherchons un majorant evaluation(S_i)≥max_{(x∈S_i)} f(x).

L’évaluation est souvent effectuée sur le problème initial après relaxation. Une relaxation permet de passer de contraintes complexes à des contraintes linéaires ou dont le dual est simple. Par exemple, une relaxation d’intégrité permet de travailler avec des variables réelles au lieu de variables entières.

Une fois que l’évaluation a été effectué, deux cas sont possibles :

Si evaluation(S_i)≥z, alors S_i ne contient aucune solution optimale, il n’est pas utile d’explorer en détail le sous-ensemble S_i.
Si evaluation(S_i)<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.

Exemple : problème du sac à dos

Un avion-cargo a une capacité de chargement de 18 unités de volume. Il doit transporter des conteneurs de marchandises de façon à maximiser la valeur totale de son chargement. Les conteneurs disponibles sont en quantité illimitée pour chaque type :

Conteneur de type A, valeur 6, volume 2;
Conteneur de type B, valeur 8, volume 3;
Conteneur de type C, valeur 13, volume 4;
Conteneur de type D, valeur 17, volume 5;
Conteneur de type E, valeur 20, volume 7.

Dans un premier temps, nous allons résoudre le problème à l’aide d’un algorithme glouton. Puis nous déterminerons la solution optimale par une procédure Branch&Bound.

La modélisation mathématique du problème est le système suivant : 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 avec x_i le nombre entier de conteneurs de type i.

La solution initiale est réalisée par l’algorithme glouton du meilleur ratio valeur/volume. Nous obtenons le vecteur de solution (1,0,0,3,0) avec z=57. x_D étant le plus grand, nous allons effectuer la séparation sur ce critère. Nous obtiendrons 4 branches pour respectivement x_D=3, 2, 1 et 0 :

x_D=3. On résout le programme linéaire relaxé ce qui donne x_C=3/4 et z=60.75. C’est une solution non admissible donc on sépare par rapport à x_A :
- x_A=1. Le problème linéaire relaxé donne x_C=1/4 et z=60.25. C’est une solution non admissible. Il n’est plus possible de séparer car il n’y a plus de x_i>0. La solution entière la plus proche revient à notre solution approchée de départ.
- x_A=0. Le problème linéaire relaxé donne x_B=1. La solution est admissible et donne z=59. On met à jour z.
x_D=2. On résout le programme linéaire relaxé ce qui donne x_C=2 et z=60. C’est une solution admissible donc on met à jour z.
x_D=1. On résout le programme linéaire relaxé ce qui donne x_C=13/4 et z=59,25. Cette borne est inférieure à z, donc on ne visite pas cette branche.
x_D=0. On résout le programme linéaire relaxé ce qui donne x_C=9/2 et z=58,5. Cette borne est inférieure à z, donc on ne visite pas cette branche.

Tout le domaine est exploré. L’optimum z*=60 a été obtenu avec le vecteur solution (0,0,2,2,0).