Une technique d'optimisation générale qui parcourt systématiquement un espace de recherche en se ramifiant en sous-problèmes et en utilisant des bornes calculées sur la meilleure solution possible dans chaque branche pour élaguer les régions qui ne peuvent contenir une solution optimale.

Principe

Combiner la ramification (décomposition de l'espace de recherche) avec le bornage (calcul de limites optimistes ou pessimistes) et une stratégie de parcours pour éliminer les branches dont les bornes indiquent qu'elles ne peuvent améliorer l'incumbent actuel.

Démonstration

Résolution d'un programme linéaire en nombres entiers en se ramifiant sur les variables fractionnaires : chaque nœud représente un sous-problème avec contraintes d'intégrité supplémentaires, et une relaxation (programme linéaire) fournit une borne supérieure ; les nœuds dont la borne de relaxation est pire que l'incumbent sont élagués. Pour le problème du voyageur de commerce, on se ramifie sur des choix de sous-tours et on utilise des bornes inférieures pour couper rapidement des branches non prometteuses.

Mauvaise application

Utiliser des bornes faibles ou lâches, des décisions de ramification médiocres ou un ordre de nœuds inadapté entraînant peu ou pas d'élagage, de sorte que l'algorithme se transforme en une recherche presque exhaustive et gaspille des calculs.

Conséquence

Avec des bornes et des heuristiques efficaces, la méthode peut réduire considérablement l'espace exploré et garantir l'optimalité à la fin ; elle permet aussi de produire des bornes valides et des solutions meilleures en cours de calcul.

Inversion

Énumération exhaustive non élaguée (recherche brute) qui examine tous les candidats sans utiliser de bornes, ou recherche purement heuristique qui ne garantit jamais l'optimalité.

Limite

S'adresse principalement aux problèmes d'optimisation discrets et combinatoires où des bornes peuvent être calculées (par ex. programmation en nombres entiers, ordonnancement combinatoire). Elle est moins adaptée aux problèmes dépourvus de relaxations calculables efficacement ou aux problèmes continus sans discrétisation/relaxation.

Tension sémantique

Tension entre la précision des bornes et leur coût de calcul : des bornes plus serrées permettent plus d'élagage mais peuvent être coûteuses à obtenir ; contraste avec les méthodes par plans de coupe ou heuristiques qui améliorent les bornes différemment ou sacrifient l'optimalité pour la vitesse.

Synthèse

Branch and bound organise une recherche exhaustive en divisant le problème en sous-problèmes et en utilisant des bornes pour éliminer les régions non prometteuses ; la performance pratique dépend de la qualité des bornes, des règles de ramification et de la sélection des nœuds, fournissant des solutions exactes si l'on va jusqu'au bout et des incumbents utiles avant cela.