Procédure Branch And Bound

Sommaire du document

Fonctionnalités de la procédure Branch And Bound

• Nous pouvons utiliser la procédure Branch And Bound en tant qu'algorithme de recherche de chemin extrême.
• Nous utiliserons la procédure Branch And Bound sur des graphes pondérés^[1]
• Nous pouvons utiliser la procédure Branch And Bound sur des graphes aux pondérations quelconques, et des graphes avec circuits ou sans circuits.

Caractéristiques de la procédure Branch And Bound

Le Branch And Bound, ou en français Procédure de séparation et d'évaluation progressive, est une application du principe "diviser pour régner" appliquée à la résolution de problèmes d'optimisation.

Nous pouvons appliquer la procédure Branch And Bound à de nombreux problèmes NP-complets, qu'il s'agisse de la théorie des graphes ou non. Parmi les exemples les plus connus, nous avons le problème du voyageur de commerce (TSP pour Traveling Salesman Problem).

La méthode Branch And Bound a longtemps été considérée comme le meilleur moyen pour la recherche de circuit hamiltonien de poids minimum (le problème du voyager de commerce), bien qu'à présent les méthodes telles que la programmation quadratique convexe^[2] ou les metaheuristiques^[3]

Séparation et évaluation

• Dans la partie séparation, nous diviserons le problème afin de constituer un "arbre de décisions".
• Dans la partie évaluation, nous déciderons vers quelle branche de l'arbre nous allons poursuivre nos investigations.

Profondeur maximale de l'arbre Branch And Bound

Dans le pire des cas nous pouvons construire un arbre qui dégénère en une liste chaînée, et que pour chaque sommet l'arc à sélectionner est le dernier. Dans ce cas, notre profondeur maximale est de n².

Dans le cas d'une optimisation en variables binaires, une variable est définie pour chaque branche, et la profondeur maximum est réduite à n.

Si nous utilisons des variables d'un autre type (par exemple en programmation en variables entières bornées), la profondeur de l'arbre Branch And Bound dépend du domaine de ce type de variable.

Algorithme de Little

L'lgorithme de Little est une simplification du Branch And Bound. Il se décompose de la manière suivante :

• Initialisation
  1. Réduction de la matrice (RM)
     • Réduction en ligne : soustraire le plus petit élément de chaque ligne, ce qui nous permet d'avoir pour chaque ligne au moins un 0.
     • Réduction en colonne : soustraire le plus petit élément de chaque colonne, ce qui nous permet d'avoir pour chaque colonne au moins un 0.
  2. Calcul de la borne inférieure (BI).
• Branch And Bound
  1. Calcul des coûts d'évitement (CE)
     CE(x,y) = min{P_xi+P_jy | i≠y ∧ j≠x}
  2. Sélection de l'arc (x,y) avec CE(x,y) maximal
  3. Branchement (création de l'arborescence)
     • Branche P₁ si nous passons par (x,y)
     • Branche P₂ si nous évitons de passer par (x,y)

A* vs Branch And Bound

A* est heuristique^[4], alors que la procédure Branch And Bound est un algorithme qui fournit la solution optimale du problème.

Comme la procédure Branch And Bound peut effectuer des backtrackings^[5] et se retrouver avec un domaine des solutions assez vaste, il peut sembler beaucoup plus lent que l'heuristique A*. Toutefois, si nous sommes pressés, nous pouvons arrêter l'algorithme Branch And Bound avant son exécution complète à partir du moment où il a trouvé au moins un chemin possible.

Nous ne sommes pas dans ce cas assurés d'être en présence du chemin optimal, mais nous avons assez rapidement un chemin parmi les meilleurs.

Notes

1. ↑ pondération : La pondération est une valeur associée à un arc (ou une arête), et correspond au coût du passage par cet arc. Par exemple, il peut s'agir d'une distance entre deux villes représentées chacune par un sommet du graphe.
   
   
2. ↑ Programmation quadratique convexe : La programmation quadratique convexe permet de réduire la taille de l'arborescence lors du "Branch And Bound".
   
   
3. ↑ Metaheuristique : Algorithmes d'optimisation. Généralement des algorithmes aléatoires qui fonctionnent par apprentissage des caractéristiques du problème pour tenter de trouver une meilleure solution.
   
   
4. ↑ Heuristique : En optimisation combinatoire et en théorie des graphes, le terme "heuristique" est utilisé pour décrire le fait que cet algorithme soit approximatif, et pas nécessairement optimal.
   
   
5. ↑ Backtracking : Si la nouvelle borne en cours de recherche est supérieure à une borne d'une branche que nous avions délaissée, nous devons remonter dans l'arbre jusqu'à cette branche et reprendre notre recherche. Le terme utilisé est le terme anglais "Backtracking".
   
   

Références

1. INFOB321 - Théorie des graphes : JP Leclercq, Cours de Théorie des Graphes et réseaux de Petri (Septembre 2008)

Ces références et liens indiquent des documents consultés lors de la rédaction de cette page, ou qui peuvent apporter un complément d'information, mais les auteurs de ces sources ne peuvent être tenus responsables du contenu de cette page.
L'auteur de ce site est seul responsable de la manière dont sont présentés ici les différents concepts, et des libertés qui sont prises avec les ouvrages de référence. N'oubliez pas que vous devez croiser les informations de sources multiples afin de diminuer les risques d'erreurs.

Structure du document