Branch and bound

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.

Sommaire

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

Wikimedia Foundation. 2010.

Contenu soumis à la licence CC-BY-SA. Source : Article Branch and bound de Wikipédia en français (auteurs)

Игры ⚽ Нужно решить контрольную?

Regardez d'autres dictionnaires:

  • Branch-and-Bound — (Verzweigung und Schranke) ist eine im Bereich Operations Research häufig verwendete mathematische Methode, deren Ziel darin besteht, für ein gegebenes ganzzahliges Optimierungsproblem eine beste Lösung zu finden. Branch and Bound führt auf einen …   Deutsch Wikipedia

  • Branch and Bound — (Verzweigung und Schranke) ist eine im Bereich Operations Research häufig verwendete mathematische Methode, deren Ziel darin besteht, für ein gegebenes ganzzahliges Optimierungsproblem eine beste Lösung zu finden. Branch and Bound führt auf einen …   Deutsch Wikipedia

  • Branch and bound — (Verzweigung und Schranke) ist eine im Bereich Operations Research häufig verwendete mathematische Methode, deren Ziel darin besteht, für ein gegebenes ganzzahliges Optimierungsproblem eine beste Lösung zu finden. Branch and Bound führt auf einen …   Deutsch Wikipedia

  • Branch and bound — (BB) is a general algorithm for finding optimal solutions of various optimization problems, especially in discrete and combinatorial optimization. It consists of a systematic enumeration of all candidate solutions, where large subsets of… …   Wikipedia

  • Branch-and-Bound-Verfahren — Branch and Bound Verfahren,   Entscheidungsbaumverfahren …   Universal-Lexikon

  • Branch-and-bound-Verfahren —   [ brɑːntʃənd baʊnd ; englisch], Operationsresearch: Entscheidungsbaumverfahren …   Universal-Lexikon

  • Branch-and-Bound-Verfahren — 1. Begriff: Verfahren des ⇡ Operations Research, bei dem ein zu lösendes kombinatorisches Optimierungsproblem (endliche Anzahl unabhängiger Variablen mit diskretem Wertevorrat) keiner effektiven analytischen Behandlung zugänglich ist oder… …   Lexikon der Economics

  • Branch and Cut — bzw. Verzweigung und Schnitt bezeichnet in der kombinatorischen Optimierung, einem Teilgebiet der diskreten Mathematik, ein Verfahren zur Lösung ganzzahliger linearer Optimierungsprobleme. Das Verfahren besteht aus der Kombination von… …   Deutsch Wikipedia

  • Branch-and-Cut — bzw. Verzweigung und Schnitt bezeichnet in der kombinatorischen Optimierung, einem Teilgebiet der diskreten Mathematik, ein Verfahren zur Lösung ganzzahliger linearer Optimierungsprobleme. Das Verfahren besteht aus der Kombination von… …   Deutsch Wikipedia

  • Branch and cut — (sometimes written as branch and cut ) is a method of combinatorial optimization for solving integer linear programs, that is, linear programming problems where some or all the unknowns are restricted to integer values. The method is a hybrid of… …   Wikipedia

Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”