No cache version.

Caching disabled. Default setting for this page:enabled (code LNG204)
If the display is too slow, you can disable the user mode to view the cached version.

Procédure Branch And Bound

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és1
  • 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 convexe2 ou les metaheuristiques3

Contents Haut

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 n2.

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.

Contents Haut

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{Pxi+Pjy | iy ∧ jx}
    2. Sélection de l'arc (x,y) avec CE(x,y) maximal
    3. Branchement (création de l'arborescence)
      • Branche P1 si nous passons par (x,y)
      • Branche P2 si nous évitons de passer par (x,y)

Contents Haut

A* vs Branch And Bound

A* est heuristique4, 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 backtrackings5 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.

English translation

You have asked to visit this site in English. For now, only the interface is translated, but not all the content yet.

If you want to help me in translations, your contribution is welcome. All you need to do is register on the site, and send me a message asking me to add you to the group of translators, which will give you the opportunity to translate the pages you want. A link at the bottom of each translated page indicates that you are the translator, and has a link to your profile.

Thank you in advance.

Document created the 03/01/2010, last modified the 26/10/2018
Source of the printed document:https://www.gaudry.be/en/graphes-branch-and-bound.html

The infobrol is a personal site whose content is my sole responsibility. The text is available under CreativeCommons license (BY-NC-SA). More info on the terms of use and the author.

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".

Contents Haut

References

  1. book Language of the document:fr INFOB321 - Théorie des graphes : JP Leclercq, Cours de Théorie des Graphes et réseaux de Petri (September 2008)

These references and links indicate documents consulted during the writing of this page, or which may provide additional information, but the authors of these sources can not be held responsible for the content of this page.
The author This site is solely responsible for the way in which the various concepts, and the freedoms that are taken with the reference works, are presented here. Remember that you must cross multiple source information to reduce the risk of errors.

Contents Haut