La méthode de branch and bound
La méthode de branch and bound
Optimisation, Mathématiques, Algorithmique · course
Fiche de révisionFiche de cours
Rédigée à partir de ce document, puis vérifiée avant publication.
Ce document présente la méthode de branch and bound, une technique d’optimisation utilisée pour résoudre efficacement des problèmes combinatoires en énumérant intelligemment les solutions possibles. Destiné aux étudiants en optimisation et algorithmique, ce matériel explique le principe général de la méthode, son algorithme, puis illustre son application à travers plusieurs problèmes classiques.
Pour de nombreux problèmes d’optimisation, l’ensemble des solutions est fini ou dénombrable. En théorie, on pourrait énumérer toutes les solutions et choisir la meilleure, mais ce processus est souvent impossible en pratique à cause du nombre très élevé de solutions. La méthode de branch and bound propose une énumération intelligente des solutions en éliminant progressivement les solutions partielles qui ne peuvent pas mener à une solution optimale. Cette élimination repose sur des bornes calculées pour chaque sous-ensemble de solutions, permettant d’écarter rapidement des branches entières de l’arbre de recherche.
La performance de la méthode dépend fortement de la qualité de la fonction de borne, qui doit être capable d’exclure tôt les solutions non prometteuses.
La méthode s’appuie sur une représentation en arborescence où la racine correspond à l’ensemble complet des solutions. Pour appliquer branch and bound, il faut :
Le processus commence par le calcul des bornes inférieure et supérieure à la racine. Si ces bornes sont égales, la solution optimale est trouvée. Sinon, l’ensemble des solutions est divisé en sous-problèmes (enfants de la racine) auxquels on applique récursivement la méthode.
Lorsqu’une solution réalisable est trouvée, elle sert à mettre à jour la borne supérieure. Toute branche dont la borne inférieure dépasse cette borne supérieure peut être éliminée, car elle ne contient pas de solution meilleure. La recherche continue jusqu’à ce que tous les nœuds soient explorés ou éliminés.
Soit un graphe G=(V,E). Un cycle est hamiltonien si tous les sommets de G apparaissent une et une seule fois dans ce cycle. Le problème du voyageur de commerce (TSP) consiste à trouver un cycle hamiltonien dont la somme des poids est minimale.
Considérons le graphe suivant (Figure 6.1) avec les poids indiqués sur les arcs :
Graphe : Sommets A, B, C, D, E avec arcs et poids associés (ex. D[i,j] représente le poids de l’arc (i,j)).
On commence la recherche à partir du sommet E. Soit v la borne inférieure initiale pour ce sommet, représentant le coût minimum possible pour toutes les solutions incluant E.
Pour chaque sommet suivant possible (A, B, C ou D), on calcule une nouvelle borne inférieure. Par exemple, pour D, la borne est :
½{(8+3)+(4+4)+(5+5)+(3+6)+(4+8)} = 25
Cette borne représente la plus petite valeur d’un cycle hamiltonien incluant les arcs (E,D) et (D,E).
Les bornes calculées pour les sommets suivants sont :
On explore en priorité la solution partielle avec la plus petite borne, ici C ou B (22.5). Ce processus se répète, mettant à jour la meilleure solution complète trouvée (par exemple une solution de coût 26) et éliminant les branches dont la borne inférieure dépasse cette valeur.
Résumé : Toute solution partielle dont la borne est supérieure à la meilleure solution connue est exclue de la recherche.
Soient n personnes à affecter à n tâches. Le coût d’affectation de la personne i à la tâche j est noté cij. Le but est de minimiser le coût total d’affectation, chaque tâche étant assignée à une seule personne.
Considérons la matrice des coûts suivante :
| Tâche 1 | Tâche 2 | Tâche 3 | Tâche 4 | |
|---|---|---|---|---|
| Personne a | 9 | 2 | 7 | 8 |
| Personne b | 6 | 4 | 3 | 7 |
| Personne c | 5 | 8 | 1 | 8 |
| Personne d | 7 | 6 | 9 | 4 |
Exemple d’affectation et de coût total :
Une borne inférieure pour ce problème est la somme des plus petits éléments de chaque ligne, ici :
2 + 3 + 1 + 4 = 10
On commence à la racine (aucune affectation choisie), avec une borne inférieure de 10. Les nœuds du premier niveau correspondent aux choix possibles pour la première personne. Le nœud le plus prometteur est celui avec la plus petite borne inférieure.
En explorant l’arbre, on trouve une solution complète avec un coût de 13. Les nœuds dont la borne inférieure dépasse cette valeur sont ignorés. Ce processus permet d’éliminer rapidement des branches non prometteuses.
On considère n tâches à exécuter successivement sur trois machines (machine 1, puis 2, puis 3). Le temps d’exécution de la tâche i sur la machine 1 est noté ai, sur la machine 2 bi, et sur la machine 3 ci. L’objectif est de trouver une permutation des tâches minimisant le temps total d’achèvement (makespan).
Exemple avec 4 tâches :
| Tâche | Machine 1 (ai) | Machine 2 (bi) | Machine 3 (ci) |
|---|---|---|---|
| 1 | 1 | 8 | 4 |
| 2 | 2 | 4 | 5 |
| 3 | 6 | 2 | 8 |
| 4 | 3 | 9 | 2 |
Le calcul du makespan pour une permutation donnée repose sur les dates de fin d’exécution sur chaque machine, notées respectivement a(ki), b(ki), g(ki) pour la tâche ki. Ces dates sont calculées récursivement :
a(k_i) = a(k_{i-1}) + a_{k_i}
b(k_i) = max(b(k_{i-1}), a(k_i)) + b_{k_i}
g(k_i) = max(g(k_{i-1}), b(k_i)) + c_{k_i}
Pour calculer une borne inférieure, on considère trois scénarios favorables, correspondant à des exécutions continues sur chaque machine :
La borne inférieure est alors :
C_max ≥ max {
a(k_i) + Σ_{U} min_{i} (b_i + c_i),
b(k_i) + Σ_{U} min_{i} (a_i + c_i),
g(k_i) + Σ_{U} min_{i} (a_i + b_i)
}
À la racine (aucune tâche exécutée), cette borne est calculée à 14, indiquant qu’aucune solution ne peut avoir un makespan inférieur à cette valeur.
En fixant la première tâche en position 1 (A={1}, U={2,3,4}), on calcule une borne inférieure à 15. En continuant ainsi, on explore l’arborescence en profondeur d’abord, mettant à jour la borne supérieure (meilleure solution complète trouvée) et éliminant les branches dont la borne inférieure dépasse cette valeur.
Le makespan de la première solution complète trouvée est 28, ce qui sert de borne supérieure pour la suite de la recherche.