Branch and Bound
- Introduite par
- Ailsa Land & Alison Doig
- Année
- 1960
- Type
- Exact combinatorial optimization algorithm
- Famille
- Mathematical programming
Ce texte est une traduction automatique et n’a pas encore été relu. Lire l’original en anglais
À quoi sert-elle ?
Branch and Bound est un algorithme exact systématique pour les problèmes d'optimisation combinatoire et entière, introduit par Ailsa Land et Alison Doig en 1960.
Il organise l'espace de recherche sous forme d'arbre de sous-problèmes, utilise des bornes supérieures dérivées de relaxations pour élaguer les branches qui ne peuvent améliorer la meilleure solution connue, et garantit la découverte d'une solution entière globalement optimale. Il constitue l'épine dorsale des solveurs modernes de programmation mixte entière utilisés en recherche opérationnelle, logistique, ordonnancement et conception d'ingénierie.
L’intuition derrière la méthode
Imaginez chercher l'objet de plus grande valeur caché dans un vaste labyrinthe de pièces. Au lieu de vérifier chaque pièce, vous estimez la valeur maximale possible atteignable depuis chaque couloir avant d'y entrer. Si ce plafond est inférieur à la meilleure pièce que vous possédez déjà, vous ignorez le couloir entier sans y regarder. Branch and Bound fonctionne de la même manière : il divise le problème en morceaux plus petits, calcule des bornes supérieures optimistes pour chaque morceau, et écarte immédiatement tout morceau qui ne peut pas, prouvablement, surpasser la meilleure solution actuelle.
Histoire
Land et Doig ont publié l'article fondateur sur Branch and Bound dans Econometrica en 1960, le présentant comme une méthode automatique pour la programmation discrète. Little et al. (1963) ont appliqué la technique au problème du voyageur de commerce, cimentant son rôle en optimisation combinatoire. Dakin (1965) a introduit le branchement par relaxation LP, la forme la plus couramment utilisée aujourd'hui. Les décennies suivantes ont vu l'intégration de plans coupants (branch-and-cut) et de génération de colonnes (branch-and-price), faisant de Branch and Bound le moteur de tous les principaux solveurs commerciaux de programmation entière.
Quand l’utiliser
Utilisez Branch and Bound lorsque vous devez trouver la solution prouvablement optimale d'un programme linéaire mixte entier ou entier pur et que vous ne pouvez pas accepter une réponse approximative. Il suppose que le problème peut être formulé avec des relaxations linéaires (ou convexes) qui fournissent des bornes utiles. Il est moins adapté aux très grandes instances où l'arbre d'énumération explose, aux programmes entiers non linéaires sans relaxations serrées, ou aux contextes temps réel où le temps de calcul est strictement limité. Dans de tels cas, des heuristiques ou métaheuristiques peuvent être préférées.
Limites et points d’attention
- La complexité dans le pire des cas est exponentielle ; sur des instances mal structurées, l'arbre peut devenir prohibitivement grand.
- La performance est très sensible au choix de la variable de branchement et de la stratégie de sélection de nœud.
- Nécessite une relaxation traitable qui fournit des bornes supérieures significatives ; des bornes faibles entraînent un élagage minimal.
- Les exigences en mémoire peuvent être substantielles lorsque de nombreux nœuds ouverts doivent être stockés simultanément.
Les conditions de la source ne remplacent ni une revue scientifique indépendante ni la validation par un moteur d’analyse.
Points forts
- Garantit l'optimalité globale pour les programmes entiers et combinatoires.
- Réduit considérablement la recherche par élagage basé sur les bornes — souvent seule une infime fraction de l'arbre d'énumération complet est explorée.
- Flexible : peut intégrer des plans coupants (branch-and-cut) ou des bornes heuristiques (branch-and-price) pour une efficacité accrue.
- Largement implémenté dans des solveurs commerciaux matures (CPLEX, Gurobi) et des outils open-source (GLPK, CBC).
Applications
- Ordonnancement d'équipage de ligne aérienne et affectation de flotte en recherche opérationnelle.
- Conception de réseaux de chaînes d'approvisionnement et problèmes de localisation d'installations.
- Disposition de circuits VLSI et allocation de registres en ingénierie informatique.
- Prédiction de structure protéique et assemblage de génomes en biologie computationnelle.
- Optimisation de portefeuille financier avec contraintes de cardinalité.
Comment ça marche
Comment ça marche
L'algorithme commence par résoudre une version relaxée du problème — typiquement la relaxation linéaire (LP) — qui ignore les contraintes d'intégrité. Cette relaxation fournit une borne supérieure sur la valeur optimale réelle car toute solution entière réalisable est également réalisable dans la relaxation. Si la solution relaxée est entière, le problème est résolu immédiatement.
Formule
\text{Solve LP relaxation: } z^* = \max\{\mathbf{c}^\top \mathbf{x} \mid A\mathbf{x} \leq \mathbf{b},\, \mathbf{x} \geq 0\}Lorsque la solution relaxée contient une variable fractionnaire, l'algorithme partitionne la région réalisable en ajoutant des contraintes complémentaires qui forcent la variable soit à son plancher, soit à son plafond. Chaque partition crée un nouveau nœud enfant dans l'arbre de recherche, divisant efficacement un sous-problème en deux sous-problèmes plus petits avec des domaines plus stricts.
Formule
\text{Select fractional variable } x_j \notin \mathbb{Z}\text{; create sub-problems: } x_j \leq \lfloor x_j^* \rfloor \text{ and } x_j \geq \lceil x_j^* \rceilChaque nœud actif reçoit sa propre borne de relaxation LP. Un nœud dont la borne ne dépasse pas la meilleure solution entière trouvée jusqu'à présent — appelée l'incumbent — ne peut pas contenir une meilleure solution, il est donc élagué. Des bornes serrées sont critiques : plus la borne est serrée, moins il faut explorer de nœuds.
Formule
\text{Compute bound } UB_k \text{ for node } k\text{; prune if } UB_k \leq z_{\text{inc}}Un nœud est expertisé (fermé définitivement) sous trois conditions : sa relaxation est infaisable, sa borne n'est pas meilleure que l'incumbent, ou sa solution relaxée est déjà entière et réalisable. Dans ce dernier cas, l'incumbent est mis à jour si la nouvelle solution l'améliore. L'algorithme se termine lorsque tous les nœuds sont expertisés, auquel cas l'incumbent est l'optimum global.
Formule
\text{Fathom node } k \text{ if infeasible, or } UB_k \leq z_{\text{inc}}, \text{ or } \mathbf{x}^*_k \in \mathbb{Z}^n\text{; update } z_{\text{inc}} \leftarrow \max(z_{\text{inc}}, z_k)Pièges courants
- Choisir mal la variable de branchement (par exemple, toujours brancher sur la première variable fractionnaire) conduit souvent à des arbres profonds et déséquilibrés et à une convergence lente.
- Ignorer les inégalités valides (plans coupants) signifie manquer l'opportunité de resserrer significativement les bornes de relaxation.
- Une terminaison prématurée avec un écart de sous-optimalité qui n'est pas signalé comme tel peut induire les praticiens en erreur en traitant une solution quasi-optimale comme exacte.
- Appliquer Branch and Bound à des relaxations non linéaires ou non convexes sans convexification spécialisée peut produire des bornes invalides et des résultats incorrects.
Questions fréquentes
En quoi Branch and Bound diffère-t-il de l'énumération exhaustive ?
L'énumération exhaustive évalue explicitement chaque solution entière réalisable, ce qui est calculatoirement infaisable pour les grands problèmes. Branch and Bound évite cela en calculant des bornes supérieures basées sur la relaxation à chaque nœud de l'arbre de recherche et en élaguant des sous-arbres entiers lorsque la borne ne peut dépasser la meilleure solution déjà trouvée. En pratique, seule une petite fraction de l'arbre est jamais examinée.
Quel est le rôle de la relaxation LP dans Branch and Bound ?
La relaxation LP supprime les contraintes d'intégrité, rendant le problème résoluble en temps polynomial par la méthode du simplexe ou des points intérieurs. Sa valeur optimale sert de borne supérieure pour le sous-problème entier correspondant. Lorsque cette borne est serrée — proche de l'optimum entier réel — moins de branches doivent être explorées. Des relaxations plus serrées, souvent obtenues en ajoutant des inégalités valides, accélèrent considérablement l'algorithme global.
Quand devrais-je utiliser Branch and Bound plutôt qu'une métaheuristique comme les algorithmes génétiques ?
Choisissez Branch and Bound lorsque vous exigez un certificat d'optimalité et pouvez vous permettre le temps de calcul. Il est idéal pour les problèmes de taille moyenne avec des relaxations LP bien structurées. Les métaheuristiques sont préférables lorsque le problème est extrêmement grand, manque d'une relaxation utile, ou doit être résolu dans un budget de temps serré où une solution quasi-optimale est acceptable. De nombreux praticiens combinent les deux : utiliser Branch and Bound avec une tolérance d'écart de terminaison précoce.
Méthodes associées
Sources
Land, A. H., & Doig, A. G. (1960). An automatic method of solving discrete programming problems. Econometrica, 28(3), 497–520.
Ouvrir la référence DOICopié.