Méthodes exactes : Branche et Liée

Cette séance de cours traite de l'algorithme Branch and Bound en optimisation discrète, qui relève le défi d'explorer un vaste ensemble de solutions réalisables en le divisant en sous-ensembles plus petits et en sélectionnant la meilleure solution. L'algorithme trouve efficacement des solutions optimales en calculant des limites inférieures sur des sous-ensembles, évitant ainsi la nécessité de résoudre exactement tous les sous-problèmes. En tirant parti de ces limites inférieures, l'algorithme Branch and Bound s'avère optimal sans résoudre tous les sous-problèmes, ce qui le rend particulièrement utile pour les grands ensembles réalisables. Dans le contexte de problèmes linéaires entiers mixtes, les limites inférieures peuvent être calculées en résolvant le problème de relaxation à laide de lalgorithme simplex.