Méthode de séparation et évaluation

La méthode de séparation et évaluation (en anglais Branch and Bound, abrégé en B&B ou BnB) est un paradigme général pour la construction d'algorithmes exacts destinés à résoudre des problèmes d'optimisation discrète et combinatoire, en particulier des problèmes NP-difficiles. La méthode consiste en une stratégie d'énumération implicite dans laquelle l'ensemble des solutions réalisables est divisé de manière séquentielle en sous-ensembles (séparation), et pour chacun d'eux, des bornes (évaluation) de la valeur de la fonction objectif sont calculées. Ces bornes permettent d'écarter (élaguer) les sous-ensembles qui ne peuvent manifestement pas contenir de solutions optimales, ce qui réduit considérablement l'espace de recherche.

La méthode a été proposée pour la première fois par A. H. Land et A. G. Doig en 1960 pour résoudre des problèmes de programmation en nombres entiers. Depuis, elle est devenue l'une des approches les plus fondamentales en recherche opérationnelle et en informatique. La caractéristique clé de la méthode est sa flexibilité : ce n'est pas un algorithme spécifique, mais plutôt un schéma stratégique de haut niveau (un framework) adaptable à la structure du problème à résoudre.

Composants clés de la méthode

La méthode repose sur trois opérations fondamentales appliquées aux sous-ensembles de l'espace des solutions, organisés sous la forme d'un arbre de recherche.

• Séparation (en anglais Branching) — C'est le processus de division récursive de l'ensemble actuel des solutions réalisables $S_i$ en plusieurs sous-ensembles plus petits, généralement disjoints, $S_{i1},S_{i2},\dots ,S_{ik}$. Chaque sous-ensemble correspond à un nouveau sous-problème et est représenté par un nœud enfant dans l'arbre de recherche. Par exemple, dans les problèmes de programmation en nombres entiers, la séparation est souvent effectuée sur une variable ayant une valeur fractionnaire dans la solution de la relaxation linéaire (PL).

• Évaluation (en anglais Bounding) — Pour chaque nœud de l'arbre de recherche (c'est-à-dire pour chaque sous-problème), une borne de la valeur de la fonction objectif est calculée. Pour un problème de minimisation, il s'agit d'une borne inférieure (lower bound), qui est une estimation garantie par le bas pour toute solution dans ce sous-ensemble. Le plus souvent, cette borne est obtenue en résolvant une relaxation du sous-problème original, une version simplifiée dans laquelle certaines contraintes complexes (comme la contrainte d'intégrité) sont temporairement ignorées. La relaxation la plus courante est la relaxation linéaire (PL).

• Élagage (en anglais Pruning) — C'est le processus consistant à éliminer de la recherche les nœuds (et les sous-arbres entiers qui leur correspondent) qui ne peuvent manifestement pas contenir de solution optimale. Un nœud est élagué dans l'un des cas suivants :

1. Élagage par borne : La borne inférieure du nœud courant n'est pas meilleure (c'est-à-dire supérieure ou égale pour un problème de minimisation) que la valeur de la meilleure solution réalisable trouvée jusqu'à présent, appelée lincumbent.
2. Élagage par faisabilité : La solution de la relaxation du nœud est réalisable pour le problème original (par exemple, toutes les variables sont entières). Cette solution est comparée à l'incumbent actuel et, si elle est meilleure, l'incumbent est mis à jour. Aucune séparation supplémentaire n'est nécessaire à partir de ce nœud.
3. Élagage par infaisabilité : Le sous-problème correspondant au nœud n'a pas de solutions réalisables.

Algorithme général

L'algorithme général de la méthode de séparation et évaluation pour un problème de minimisation peut être décrit par les étapes suivantes :

1. Initialisation : Trouver une solution réalisable initiale (par exemple, à l'aide d'une heuristique) et définir sa valeur comme borne supérieure initiale (incumbent) $U$. Créer une liste de nœuds actifs $Q$ contenant le nœud racine (le problème initial).
2. Boucle principale : Tant que la liste $Q$ n'est pas vide :
   • Sélectionner un nœud de $Q$ selon une stratégie de recherche (par exemple, recherche en profondeur d'abord ou recherche du meilleur d'abord).
   • Résoudre la relaxation pour ce nœud afin d'obtenir une borne inférieure $L$.
   • Élaguer le nœud si $L\ge U$.
   • Si la solution de la relaxation est réalisable pour le problème original, mettre à jour l'incumbent : $U\leftarrow L$.
   • Si le nœud n'est pas élagué et que la solution n'est pas réalisable, effectuer une séparation en le divisant en nœuds enfants, et les ajouter à la liste $Q$.
3. Terminaison : Lorsque la liste $Q$ est vide, l'algorithme se termine. La solution correspondant à l'incumbent $U$ est l'optimum global.

Propriétés clés et théorèmes

• Correction et convergence : L'algorithme garantit de trouver une solution optimale globale en un nombre fini d'étapes, si l'ensemble des solutions réalisables est fini et si la procédure de séparation est convergente (c'est-à-dire que, par divisions récursives, les sous-ensembles se « contractent » vers des points uniques).
• Stratégie de recherche : L'efficacité de l'algorithme dépend fortement de la stratégie de sélection du prochain nœud à explorer (par exemple, recherche en profondeur d'abord, en largeur d'abord, ou du meilleur d'abord) et du choix de la variable de séparation. Les solveurs modernes utilisent souvent des stratégies hybrides.

Exemples

• Programmation en nombres entiers : Une application classique de la méthode. La programmation linéaire est utilisée comme relaxation. La séparation est effectuée sur une variable fractionnaire $x_j$, créant deux sous-problèmes avec les contraintes supplémentaires $x_j\le \lfloor x_j^{*}\rfloor$ et $x_j\ge \lceil x_j^{*}\rceil$.
• Problème du voyageur de commerce : L'espace des solutions est l'ensemble de tous les cycles hamiltoniens possibles dans un graphe. La séparation peut être effectuée sur les arêtes (inclure/exclure une arête du chemin). Les bornes inférieures peuvent être obtenues en résolvant des problèmes plus simples, comme le problème d'affectation ou la construction d'un arbre couvrant de poids minimum.

Concepts et applications connexes

• Méthode de séparation et coupe (Branch-and-Cut) : Une méthode hybride qui combine la séparation et évaluation avec la méthode des plans sécants. À chaque nœud de l'arbre de recherche, en plus de résoudre la relaxation, des inégalités supplémentaires (les coupes) sont générées pour renforcer la borne inférieure, ce qui conduit à un élagage plus efficace des branches.
• Retour sur trace (Backtracking) : La méthode de séparation et évaluation peut être considérée comme une généralisation de cet algorithme pour les problèmes d'optimisation.
• Élagage alpha-bêta : Une analogie conceptuelle utilisée dans les arbres de jeu pour élaguer les branches manifestement perdantes.

Voir aussi

• Programmation en nombres entiers
• Optimisation combinatoire
• Problème du voyageur de commerce
• Problème NP-difficile
• Algorithme du simplexe