Branch and bound

Séparation et évaluation

Un algorithme par séparation et évaluation, également appelé selon le terme anglo-saxon branch and bound, est une méthode générique de résolution de problèmes d'optimisation, et plus particulièrement d'optimisation combinatoire ou discrète. C'est une méthode d'énumération implicite : toutes les solutions possibles du problème peuvent être énumérées mais, l'analyse des propriétés du problème permet d'éviter l'énumération de larges classes de mauvaises solutions. Dans un bon algorithme par séparation et évaluation, seules les solutions potentiellement bonnes sont donc énumérées.

Le branch and bound est parfois comparé à une autre technique de recherche de solution, l'algorithme A*, très souvent utilisé en intelligence artificielle, alors que le branch and bound est plutôt dédié aux problèmes de recherche opérationnelle.

Présentation de la méthode

La méthode est volontairement présentée dans un cadre relativement simple pour éviter des problèmes techniques qui nuiraient à la clarté de l'exposé.

Soit S un ensemble fini mais de « grande » cardinalité qu'on appelle ensemble (ou espace) des solutions réalisables. On dispose d'une fonction f qui, pour toute solution réalisable x de S, renvoie un coût f(x). Le but du problème est de trouver la solution réalisable x de coût minimal. D'un point de vue purement existentiel, le problème est trivial : une telle solution x existe bien car l'ensemble S est fini. En revanche, l'approche effective du problème se confronte à deux difficultés. La première est qu'il n'existe pas forcément un algorithme simple pour énumérer les éléments de S. La seconde est que le nombre de solutions réalisables est très grand, ce qui signifie que le temps d'énumération de toutes les solutions est prohibitif (la complexité algorithmique est en général exponentielle).

Dans les méthodes par séparation et évaluation, la séparation permet d'obtenir une méthode générique pour énumérer toutes les solutions tandis que l'évaluation évite l'énumération systématique de toutes les solutions.

Séparation

La phase de séparation consiste à diviser le problème en un certain nombre de sous-problèmes qui ont chacun leur ensemble de solutions réalisables de telle sorte que tous ces ensembles forment un recouvrement (idéalement une partition) de l'ensemble S. Ainsi, en résolvant tous les sous-problèmes et en prenant la meilleure solution trouvée, on est assuré d'avoir résolu le problème initial. Ce principe de séparation peut être appliqué de manière récursive à chacun des sous-ensembles de solutions obtenus, et ceci tant qu'il y a des ensembles contenant plusieurs solutions. Les ensembles de solutions (et leurs sous-problèmes associés) ainsi construits ont une hiérarchie naturelle en arbre, souvent appelée arbre de recherche ou arbre de décision.

Évaluation

L'évaluation d'un nœud de l'arbre de recherche a pour but de déterminer l'optimum de l'ensemble des solutions réalisables associé au nœud en question ou, au contraire, de prouver mathématiquement que cet ensemble ne contient pas de solution intéressante pour la résolution du problème (typiquement, qu'il n'y a pas de solution optimale). Lorsqu'un tel nœud est identifié dans l'arbre de recherche, il est donc inutile d'effectuer la séparation de son espace de solutions.

À un nœud donné, l'optimum du sous-problème peut être déterminé lorsque le sous-problème devient « suffisamment simple ». Par exemple, lorsque l'ensemble des solutions réalisables devient un singleton, le problème est effectivement simple : l'optimum est l'unique élément de l'ensemble. Dans d'autres cas, il arrive que par le jeu des séparations, on arrive à un sous-problème dans lequel les décisions « difficiles » ont été prises et qui peut ainsi être résolu en temps polynomial.

Pour déterminer qu'un ensemble de solutions réalisables ne contient pas de solution optimale, la méthode la plus générale consiste à déterminer une borne inférieure pour le coût des solutions contenues dans l'ensemble (s'il s'agit d'un problème de minimisation). Si on arrive à trouver une borne inférieure de coût supérieur au coût de la meilleure solution trouvée jusqu'à présent, on a alors l'assurance que le sous-ensemble ne contient pas l'optimum. Les techniques les plus classiques pour le calcul de bornes sont basées sur l'idée de relaxation de certaines contraintes : relaxation continue, relaxation lagrangienne, etc.

Détails

La qualité de l'exploration repose grandement sur le choix d'une heuristique dont on suppose qu'elle aura plus de chance de faire venir le meilleur résultat dans les premiers. Par exemple, dans un problème du voyageur de commerce, on ne choisit pas en priorité de passer d'une ville à la ville la plus éloignée ! De cette manière, on augmente la probabilité de trouver de bonnes solutions réalisables dès le début de la recherche.

Le programme mémorise aussi la croissance ou décroissance de la fonction objectif au fil du temps, afin de suggérer éventuellement des temps d'exploration plus longs si des gains importants ont été obtenus vers la fin de la période de recherche.

On peut, bien que ce ne soit pas obligatoire, mémoriser aussi les meilleures solutions trouvées au fur et à mesure qu'on les trouve. La suite des réorganisations conduisant à de meilleurs résultat peut en effet à son tour aiguiller vers de nouvelles heuristiques.

Il est également possible de munir le programme d'un test de clé pupitre, d'interaction utilisateur par le moyen du clavier ou de chronométrage assurant qu'il s'arrêtera au bout d'un temps compatible avec le budget, et en imprimant alors le meilleur résultat trouvé à ce moment-là (les résultats sont souvent imprimés ou affichés au fur et à mesure, ce qui permet de savoir quand s'arrêter).

Perfectionnements

• Pour pallier l'imperfection des heuristiques, le programme est souvent muni de métaheuristiques permettant d'abandonner momentanément une exploration quand elle ne donne pas le rendement souhaité (par exemple chemin plus long en 5 étapes qu'en 25 étapes par un chemin antérieur, ce qui n'augure pas forcément bien de la suite).

• Lorsque l'exploration d'arbre se fait contre un joueur adverse, on utilise un autre court-circuit d'esprit voisin qui est l'élagage alpha-beta (parfois nommée coupure P-Q).

Champs d'application

Cette technique est très couramment utilisée dans le domaine de la recherche opérationnelle pour résoudre les problèmes de la classe NP. Elles sont en particulier au cœur des solveurs de programmation linéaire en nombres entiers et de programmation par contraintes.

Ce document provient de « S%C3%A9paration et %C3%A9valuation ».