La méthode de branch and bound

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.

Introduction à la méthode de branch and bound

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.

L’algorithme général de branch and bound

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 :

• Un moyen de calculer une borne inférieure pour une solution partielle.
• Une stratégie pour subdiviser l’espace de recherche en sous-espaces plus petits.
• Un moyen de calculer une borne supérieure pour au moins une solution réalisable.

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.

Illustrations de la méthode sur des problèmes classiques

Le problème du voyageur de commerce

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 :

• C : 22.5
• A : 23
• B : 22.5
• D : 25

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.

Le problème d’affectation

Soient n personnes à affecter à n tâches. Le coût d’affectation de la personne i à la tâche j est noté c_ij. 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 :

• (1, a), (2, c), (3, b), (4, d) → coût = 9 + 8 + 3 + 4 = 24
• (1, b), (2, c), (3, d), (4, a) → coût = 6 + 8 + 9 + 8 = 31

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.

Le problème de flow shop à trois machines

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é a_i, sur la machine 2 b_i, et sur la machine 3 c_i. 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(k_i), b(k_i), g(k_i) pour la tâche k_i. 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 :

• Machine 1 continue : C_max ≥ a(k_i) + Σ_{U} (b_i + c_i) minimum
• Machine 2 continue : C_max ≥ b(k_i) + Σ_{U} (a_i + c_i) minimum
• Machine 3 continue : C_max ≥ g(k_i) + Σ_{U} (a_i + b_i) minimum

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.

Glossaire des termes clés

• Branch and bound : Méthode d’optimisation combinatoire qui explore un arbre de solutions partielles en éliminant celles qui ne peuvent pas conduire à une solution optimale grâce à des bornes.
• Borne inférieure : Valeur minimale possible du coût ou critère d’une solution partielle, utilisée pour écarter des branches non prometteuses.
• Borne supérieure : Coût d’une solution réalisable connue, servant de référence pour éliminer les solutions partielles plus coûteuses.
• Cycle hamiltonien : Cycle dans un graphe passant une et une seule fois par chaque sommet.
• Problème du voyageur de commerce (TSP) : Trouver un cycle hamiltonien de coût minimal dans un graphe valué.
• Problème d’affectation : Assigner n personnes à n tâches en minimisant le coût total, avec une tâche par personne.
• Flow shop : Problème de planification où n tâches doivent être exécutées dans le même ordre sur plusieurs machines.
• Makespan : Temps total d’achèvement d’un ensemble de tâches dans un problème de planification.
• Arborescence : Structure en arbre représentant l’espace de recherche des solutions partielles dans branch and bound.

Points clés à retenir

• La méthode de branch and bound permet de résoudre des problèmes d’optimisation en explorant intelligemment l’espace des solutions.
• Elle repose sur le calcul de bornes inférieures et supérieures pour éliminer des sous-ensembles de solutions non prometteurs.
• La qualité de la fonction de borne est cruciale pour la performance de la méthode.
• La méthode s’applique à divers problèmes, notamment le voyageur de commerce, le problème d’affectation et le flow shop.
• L’exploration peut se faire selon différentes stratégies (profondeur d’abord, largeur d’abord), chacune ayant ses avantages.
• Le processus s’arrête lorsque toutes les branches sont explorées ou éliminées, garantissant la solution optimale.