Le 12/06/2015 par etudiantero :

j'ai un pb de minimisation à résoudre avec le branch and bound. mais j'ai un probleme avec la comprehension des bornes
devrai je avoir au départ une borne inf ou sup et pourquoi et les borne se calculent à chaque noeud de l'arbre ou une seule fois.
rq:si vous avez des exemples simples et clairs ou des liens qui expliquent bien le principe des bornes veuillez me l'indiquer
merci pour votre aide

Le 15/06/2015 par rapine5 :

L'algorithme de Branch & Bound maintient une borne supérieure (UB) et inférieure (LB) au noeud racine. L'algorithme s'arrête lorsque que les bornes sont égales (ou la différence < % défini). Dans le cas de la résolution d'un MIP :
- UB est la meilleure solution réalisable connue. Une solution réalisable est trouvée par l'algorithme aux feuilles de l'arbre d'énumération, et parfois avec un peu de chance comme solution de la relaxation linéaire à un noeud. On peut bien sûr utiliser en plus des heuristiques pour en générer au cours de l'exploration et espérer accélérer la recherche.
-LB est une borne inférieure du problème. A chaque noeud x, la borne inférieure LB(x) pour le sous-problème correspondant est calculée, par relaxation linéaire. Ceci permet éventuellement d'éliminer le noeud de la recherche si LB(x) > UB. Ceci permet aussi (et surtout) de mettre à jour la borne inférieure de son père. En effet, la borne inférieure d'un noeud doit être supérieure à la plus petite des bornes inférieures de ces fils. Les bornes inférieures sont ainsi mis à jour de proche en proche, éventuellement jusqu'au noeud racine. Mais la valeur LB de la racine augmente en générale très lentement.