Chapitre 4.Modélisation du problème
posé
La Méthode par séparation et évaluation
(Branch and Bound)
L'algorithme de séparation et évaluations, plus
connu sous son appellation anglaise Branch and Bound (B&B) est une
méthode exacte, appartient à la famille de recherche arborescente
qui est utilisée pour la résolution des programmes
mathématiques (P). Le principe de cette méthode consiste à
faire une énumération des solutions admissibles en gardant pour
objectif de ne pas développer tout l'arbre de recherche en "coupant" des
branches à l'aide de bornes. Le Branch-and-Bound est composé de
deux étapes : évaluation et séparation. [10]
· La séparation: cette phase consiste à
diviser le problème initial en plusieurs sous-problèmes qui ont
chacun un ensemble de solutions réalisables, en résolvant tous
les sous-problèmes et en gardant la meilleure solution on assure la
résolution de notre problème initial. L'ensemble de solutions
construit une hiérarchie en arbre souvent appelée arbre de
décision.
· L'évaluation : l'évaluation d'un noeud
de l'arbre de décision a pour but de déterminer l'optimum de
l'ensemble des solutions réalisables associés au noeud en
question ou bien le contraire, c'est à dire de prouver
mathématiquement que cet ensemble ne contient pas de solution optimale
pour la résolution du problème.
4.4.2 Les Méthodes approchées
Les méthodes de résolution approchées
sont connues sous le nom d'heuristiques ou de méta-heuristiques. Elles
ont pour but de trouver une solution admissible en un temps raisonnable, mais
sans garantir l'optimalité de cette solution. Ces méthodes sont
utilisées pour résoudre des problèmes de grandes tailles
en temps de calcul acceptable.
Les heuristiques
Une heuristique est un algorithme de résolution qui
fournit une solution réalisable mais pas nécessairement optimale,
pour un problème d'optimisation combinatoire. La différence entre
les méthodes heuristiques et les méthodes algorithmiques est que
ces derniers ne nous assurent pas qu'on va arriver à un résultat
en un nombre fini d'étapes.
| 
