Séparation et évaluation

Un algorithme par séparation et évaluation, ou branch and bound en anglais, est une méthode générique de résolution de problèmes d'optimisation combinatoire. Cet algorithme a été introduit par Ailsa Land et Alison Harcourt (Doig) en 1960.

L'optimisation combinatoire consiste à trouver un point minimisant une fonction, appelée coût, dans un ensemble dénombrable. Une méthode naïve pour résoudre ce problème est d'énumérer toutes les solutions du problème, de calculer le coût pour chacune, puis de donner le minimum. Parfois, il est possible d'éviter d'énumérer des solutions dont on sait, par l'analyse des propriétés du problème, que ce sont de mauvaises solutions, c'est-à-dire des solutions qui ne peuvent pas être le minimum. La méthode séparation et évaluation est une méthode générale pour cela.

Cette méthode est très utilisée pour résoudre des problèmes NP-complets, c'est-à-dire des problèmes considérés comme difficiles à résoudre efficacement.

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 destiné aux problèmes de recherche opérationnelle.

Contexte : problème d'optimisation

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é en temps 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.

Présentation de la méthode

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 un minorant du coût des solutions contenues dans l'ensemble (s'il s'agit d'un problème de minimisation). Si on arrive à trouver un minorant qui est 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 minorants sont fondées sur l'idée de relaxation de certaines contraintes : relaxation continue, relaxation lagrangienne, etc.

Techniques de sélection

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. 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ésultats 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).

Techniques d'évaluation

Une bonne fonction d'évaluation est essentielle pour que la méthode soit efficace. Le but d'une fonction d'évaluation est de donner une estimation la plus proche possible de la valeur exacte, c'est-à-dire du plus petit coût dans le sous-problème. Il y a cependant un compromis à faire entre la qualité et le temps de calcul.

Deux techniques classiques sont l'utilisation de relaxations et la modification de la fonction de coût.

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

• 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-bêta (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 NP-complets. Elles sont en particulier au cœur des solveurs d'optimisation linéaire en nombres entiers et de programmation par contraintes.

Voir aussi

• Retour sur trace

Lien externe

• Djamal Rebaïne, « Note de cours : La méthode de branch and bound », sur Université du Québec à Chicoutimi