Branch and Bound
Le branch and bound explore l'espace des solutions en branchant et élague les sous-arbres qui ne peuvent contenir l'optimum à l'aide de bornes ; il sert en optimisation discrète.
Objectif
Résoudre exactement des problèmes d'optimisation combinatoire, en accélérant la recherche par élagage.
Mécanisme
On maintient une meilleure borne globale. Brancher : diviser le problème en sous-problèmes. Borner : calculer une borne inférieure/supérieure pour chaque sous-problème et élager si la borne ne bat pas la meilleure actuelle. Courant en programmation en nombres entiers et pour le TSP.
Cas d’usage
- Programmation en nombres entiers
- Résolution du TSP
- Optimisation combinatoire