Application de l'algorithme de branch and bound (Programmation linéaire en nombres entiers)

Cette vidéo aborde l'algorithme de Branch and Bound en l'appliquant sur un petit exemple. On y parle de:

Relaxation linéaire: relâcher les contraintes d'intégralité i.e autoriser les variables à prendre des valeurs fractionnaires
Résolution graphique de la relaxation linéaire, comment être efficace
Principe d'élagage de l'arbre s'appuyant sur la relaxation linéaire et la meilleure solution réalisable connue
Premières intuitions sur la notion de qualité de formulation.

Le branch and bound peut réussir à trouver et prouver la solution optimale, c'est un algorithme exact. Il ne fait pas une exploration explicite toutes les combinaisons possibles des valeurs entières car c'est impossible en pratique mais réalise une exploration implicite de certaines parties de l'arbre. En élaguant un sous-arbre avec la relaxation linéaire, c'est comme si on l'avait exploré sans le faire vraiment, on prouve que le sous-arbre ne peut pas contenir de solutions améliorantes, c'est une exploration implicite (et beaucoup plus rapide...).


À voir après (qualité de formulation):    • Qualité de formulation en PLNE: prése...