La méthode branch and bound, ou séparation et évaluation en français, est l’un des grands outils de l’optimisation combinatoire. Elle permet de chercher une solution optimale sans devoir tester aveuglément toutes les possibilités, ce qui la rend précieuse pour résoudre des problèmes difficiles comme l’affectation de tâches, la planification, le routage ou la sélection d’investissements.
Le principe du branch and bound repose sur une idée simple : lorsqu’un problème comporte trop de combinaisons pour être résolu par énumération complète, il faut organiser la recherche et éliminer le plus tôt possible les pistes inutiles. Au lieu de parcourir toutes les solutions une par une, l’algorithme construit un arbre de recherche, dans lequel chaque branche représente une décision partielle.
Cette approche est particulièrement utilisée pour les problèmes d’optimisation où l’on cherche la meilleure solution selon un critère donné : minimiser un coût, maximiser un gain, réduire une distance ou respecter des contraintes. Elle s’applique notamment à des problèmes NP-difficiles, pour lesquels le nombre de solutions possibles augmente très vite avec la taille des données.
Le branch and bound appartient à la famille des méthodes exactes. Contrairement à une heuristique, il ne se contente pas de produire une bonne réponse : lorsqu’il termine correctement, il fournit une solution dont l’optimalité est garantie. C’est ce qui explique son intérêt dans les contextes où une approximation ne suffit pas, par exemple en logistique, en finance, en recherche opérationnelle ou en conception industrielle.
La première partie de la méthode est le branching, ou branchement. Elle consiste à diviser un problème complexe en sous-problèmes plus simples. Chaque sous-problème correspond à un ensemble restreint de solutions possibles, défini par une décision déjà prise. Dans un problème de sac à dos, par exemple, une branche peut représenter le choix d’inclure un objet, tandis qu’une autre représente le choix de l’exclure.
À mesure que l’arbre se développe, l’algorithme précise progressivement la solution. Au sommet, aucune décision n’a encore été prise. Plus on descend dans l’arbre, plus les choix deviennent spécifiques. Une feuille de l’arbre correspond en général à une solution complète, qui peut alors être évaluée précisément.
Cette logique de division permet de structurer la recherche. Mais si l’algorithme devait développer tout l’arbre, il reviendrait à tester toutes les combinaisons. Le véritable intérêt du branch and bound vient donc de sa deuxième composante : la capacité à couper certaines branches avant même de les explorer jusqu’au bout.
La partie bound, ou évaluation par bornes, est le cœur de la méthode. Pour chaque sous-problème, l’algorithme calcule une estimation optimiste de ce qu’il est encore possible d’obtenir. Dans un problème de minimisation, il s’agit d’une borne inférieure : aucun résultat dans cette branche ne pourra être meilleur que cette valeur. Dans un problème de maximisation, on utilise une borne supérieure.
Cette estimation est comparée à la meilleure solution complète déjà trouvée, souvent appelée solution incumbent. Si la borne montre qu’une branche ne peut pas produire une solution plus intéressante, l’algorithme l’abandonne. C’est ce que l’on appelle l’élagage, ou pruning en anglais.
Imaginons un problème où l’on cherche à minimiser un coût. Si la meilleure solution connue coûte 120 et qu’un sous-problème ne peut pas descendre sous 135, il est inutile de poursuivre cette branche. Même dans le meilleur des cas, elle ne battra pas la solution actuelle. Ce mécanisme permet de réduire massivement l’espace de recherche grâce à une élimination raisonnée des options.
Même si les détails varient selon le problème, un algorithme branch and bound suit généralement un déroulement stable. Il commence par initialiser une solution de référence, parfois obtenue avec une méthode simple. Puis il explore les sous-problèmes, calcule leurs bornes, conserve les pistes prometteuses et écarte celles qui ne peuvent plus améliorer le résultat.
Le processus continue jusqu’à ce qu’il n’existe plus de sous-problèmes à examiner. À ce moment-là, la meilleure solution conservée est déclarée optimale. La force de la méthode vient donc de cette combinaison entre exploration systématique et réduction intelligente du nombre de cas à traiter.
Le problème du sac à dos illustre bien le fonctionnement du branch and bound. On dispose d’un ensemble d’objets, chacun ayant un poids et une valeur, et l’objectif consiste à sélectionner les objets qui maximisent la valeur totale sans dépasser une capacité donnée. Le nombre de combinaisons possibles peut devenir très élevé dès que le nombre d’objets augmente.
L’algorithme commence par considérer le problème global. Il crée ensuite deux branches : dans l’une, un premier objet est choisi ; dans l’autre, il ne l’est pas. Pour chaque branche, il estime la meilleure valeur encore atteignable, par exemple en utilisant une version relâchée du problème où l’on autorise des fractions d’objets. Cette estimation fournit une borne optimiste.
Si une branche ne peut pas dépasser la meilleure combinaison déjà trouvée, elle est écartée. L’algorithme se concentre alors sur les branches les plus prometteuses. Dans les cas favorables, seule une petite partie de l’arbre est réellement explorée. Le résultat final reste exact, mais le temps de calcul peut être bien inférieur à celui d’une recherche exhaustive.
La qualité des bornes influence directement l’efficacité du branch and bound. Une borne trop grossière élimine peu de branches, ce qui laisse l’algorithme explorer un grand nombre de sous-problèmes. Une borne précise permet au contraire de détecter rapidement les pistes sans avenir. Tout l’enjeu consiste donc à trouver un bon équilibre entre coût de calcul et précision de l’estimation.
Dans certains problèmes, les bornes sont obtenues par relaxation. On simplifie temporairement une contrainte pour rendre le problème plus facile à résoudre. Le résultat de ce problème simplifié sert ensuite de limite théorique. Cette logique est fréquente en programmation linéaire, en optimisation combinatoire et dans de nombreux solveurs professionnels.
La manière de choisir le prochain nœud à explorer compte également. Certaines stratégies privilégient la branche la plus prometteuse, d’autres explorent en profondeur pour trouver vite une solution complète. Une bonne solution initiale peut accélérer l’élagage, car elle donne un seuil plus exigeant dès le départ. C’est un point commun avec les méthodes gloutonnes, dont l’analyse de la preuve d’optimalité d’un choix local aide à comprendre les différences entre décision rapide et garantie globale.
Le principal avantage du branch and bound est sa capacité à fournir une solution optimale certifiée. Pour les entreprises ou les chercheurs, cette garantie peut être essentielle. Elle permet de justifier une décision, de comparer des scénarios et de vérifier qu’aucune solution meilleure n’a été ignorée. C’est une qualité rare face à des problèmes où les combinaisons sont extrêmement nombreuses.
La méthode est aussi très flexible. Elle peut être adaptée à des domaines variés : ordonnancement de production, tournées de véhicules, allocation de ressources, placement de composants, choix de portefeuille ou résolution de programmes en nombres entiers. Les solveurs modernes utilisent souvent des variantes sophistiquées, enrichies par des coupes, des heuristiques et des techniques de prétraitement.
Sa limite majeure reste le temps de calcul. Dans le pire des cas, le branch and bound peut encore devoir explorer une très grande partie de l’arbre. Lorsque les bornes sont faibles ou que les contraintes discriminent mal les solutions, la méthode devient coûteuse. C’est pour cette raison que des approches alternatives, comme les heuristiques et métaheuristiques, sont parfois préférées lorsque l’on accepte une solution de très bonne qualité sans garantie absolue ; ce compromis est central dans le traitement pratique des problèmes NP-difficiles.
Branch and bound n’est pas une formule miracle. Son efficacité dépend fortement de la modélisation du problème, de la pertinence des bornes, de l’ordre d’exploration et de la qualité des solutions initiales. Deux implémentations différentes peuvent produire le même résultat optimal, mais avec des temps de calcul très éloignés.
Dans la pratique, les spécialistes cherchent souvent à renforcer l’algorithme en combinant plusieurs techniques. Une heuristique peut fournir une bonne solution de départ. Une relaxation plus fine peut améliorer les bornes. Des règles de dominance peuvent supprimer des cas redondants. Ces optimisations ne changent pas le principe fondamental, mais elles rendent la méthode beaucoup plus performante sur des instances réelles.
Il faut aussi distinguer la théorie et l’usage. Théoriquement, la complexité peut rester exponentielle. Mais dans de nombreux cas concrets, un branch and bound bien conçu résout efficacement des problèmes impossibles à traiter par une simple énumération. C’est cette capacité à conjuguer rigueur mathématique et pragmatisme algorithmique qui explique sa longévité.
La méthode branch and bound fonctionne en divisant un problème en sous-problèmes, puis en éliminant ceux qui ne peuvent pas mener à une meilleure solution. Le branchement organise l’exploration, tandis que les bornes permettent de couper les chemins inutiles. À la fin, si tous les sous-problèmes ont été résolus ou écartés correctement, la solution obtenue est mathématiquement optimale.
Son intérêt est particulièrement fort pour les problèmes d’optimisation combinatoire, où le nombre de possibilités rend l’exploration naïve irréaliste. Elle reste cependant dépendante de la qualité des bornes et peut devenir coûteuse sur les instances les plus difficiles. En résumé, le branch and bound est une méthode précise, structurée et puissante, qui illustre parfaitement l’art de chercher moins pour trouver mieux.
