La méthode Branch&Bound

Définition et historique :

La procédure de séparation et d'évaluation progressive, est une mise en application du principe latin

"Divide ut Regnes" qui conseille de diviser ses ennemis pour régner plus aisément. La méthode de Séparation et

d’Évaluation progressive (PSE), est une méthode exacte d’optimisation basée sur une énumération contrôlée

qui fournit, en général, une solution optimale. Il s'agit d'une procédure d'optimisation donc de maximisation ou

de minimisation d'une fonction F dite fonction objectif sur un domaine D de solutions possibles. La méthode

B&B a été proposée pour la première fois par A. H. Land and A. G. Doig en 1960 pour la programmation

discrète.

L’algorithme général de la méthode :

L’algorithme général correspondant à la procédure de séparation et d’évaluation (PSE) est le suivant :

Étape 1

Initialisation :

Calculer une borne supérieure BS (ou inférieur selon le critère à optimiser).

Étape 2

Séparation :

Sélectionner le sommet (l’espace de recherche) à séparer et créer ses fils (branches).

Étape 3

Évaluation :

Chercher une borne supérieure (inférieure) d’une fonction objective relative à chaque sous-espace de recherche,

Étape 4

Élimination :

Éliminer les mauvais sous-espaces (suivant le cas : maximisation ou minimisation).

Étape 5

Critère d'arrêt

Si tous les sommets ont été éliminés alors arrêter.

Sinon aller à l’étape 2 jusqu’à obtenir l’optimum global.

Avantage et inconvénients :

La méthode B&B pratique une énumération intelligente de l’espace des solutions elle est appliquée à des

problèmes NP-difficiles sa complexité en moyenne est bien plus faible Mais Cette méthode reste bien sûr

exponentielle, pour des problèmes de grande taille, sa durée d’exécution devient prohibitive, et il faut se tourner

vers des heuristiques.