branch-and-bound algorithm

Imaginez un sac qui ne peut porter que 6 kg et plusieurs objets parmi lesquels choisir. Tester toutes les combinaisons donnerait la meilleure, mais leur nombre peut vite exploser. La séparation et évaluation organise les choix en branches : prendre un objet ou le laisser. Pour chaque branche, elle estime le meilleur gain encore possible. Si même cette estimation ne dépasse pas une solution déjà trouvée, toute la branche est abandonnée sans examiner chaque combinaison.

La séparation et évaluation, ou branch-and-bound, est une méthode exacte d’optimisation combinatoire. Elle représente l’ensemble des solutions admissibles par un arbre de sous-problèmes. La séparation partage un sous-problème en cas plus restreints dont la réunion couvre tous les choix qui restent à étudier. L’évaluation associe à chaque cas une borne valide sur la meilleure valeur qu’il peut encore contenir.

Dans un problème de maximisation, la meilleure solution admissible connue fournit une valeur de référence, appelée valeur de l’incumbent. Une borne supérieure surestime, ou atteint, le gain réalisable dans un sous-problème. Si cette borne ne dépasse pas la valeur de l’incumbent, le sous-problème peut être élagué. En notant U(S) la borne supérieure du sous-problème S et z^* la valeur de l’incumbent, le critère est :Pour une minimisation, on emploie symétriquement une borne inférieure et on élague lorsqu’elle est au moins égale à la meilleure valeur connue.

La méthode est exacte si les séparations n’omettent aucune solution admissible, si les bornes sont valides et si l’exploration se termine. Elle peut ainsi traiter des problèmes NP-difficiles, notamment le problème du sac à dos et le problème du voyageur de commerce, sans garantir pour autant un temps de calcul court.

Pour maximiser une valeur, on conserve chaque solution admissible qui améliore la meilleure valeur connue ; cette référence peut être absente au départ. On sépare le problème en sous-problèmes couvrant tous les choix restants, puis on calcule pour chacun une borne supérieure valide. Un sous-problème est fermé s’il est impossible, entièrement résolu, ou si sa borne ne dépasse pas la meilleure valeur obtenue. Sinon, il est à son tour séparé. Quand aucun sous-problème ouvert ne subsiste, la meilleure solution conservée est optimale. Pour une minimisation, les inégalités sont inversées.

La méthode s’applique lorsqu’un problème d’optimisation peut être découpé en sous-problèmes qui couvrent toutes les solutions admissibles. Il faut pouvoir reconnaître une solution admissible, comparer ses valeurs et calculer une borne prouvée pour chaque sous-problème. Dans un espace fini, ces conditions et une séparation qui progresse assurent la terminaison. Dans un espace infini, une règle de convergence supplémentaire est nécessaire.

Une estimation seulement plausible ne suffit pas. Par exemple, si une prétendue borne supérieure vaut 50 alors qu’une solution de valeur 56 reste possible dans la branche, l’élagage peut supprimer l’optimum. Il faut alors construire une relaxation donnant une vraie borne, ou employer une méthode heuristique en acceptant qu’elle ne certifie pas l’optimalité.

Un sac accepte au plus 6 kg. Trois objets sont disponibles : A pèse 4 kg et vaut 40 points ; B pèse 3 kg et vaut 27 points ; C pèse 2 kg et vaut 16 points. Chaque objet est pris au plus une fois. La solution A + C est admissible : elle pèse 6 kg et vaut 56 points. Elle devient l’incumbent. Pour borner une branche, on autorise provisoirement une fraction du prochain objet, ce qui ne peut que surestimer le gain entier.

1. À la racine, A remplit 4 kg et deux tiers de B remplissent les 2 kg restants : la borne supérieure vaut 40 + 18 = 58 points.
2. Si A est exclu, B + C pèsent 5 kg et valent au plus 27 + 16 = 43 points. Comme 43 < 56, cette branche est élaguée.
3. Si A est inclus, inclure aussi B dépasserait 6 kg : cette branche est impossible.
4. En excluant B, A + C donne exactement 56 points. Si C est aussi exclu, il ne reste que A, qui vaut 40 points et ne peut donc pas battre 56. Toutes les autres branches sont fermées ; A + C est donc optimale. L’arbre de décision rend visibles la borne, l’impossibilité et l’élagage qui fondent ce certificat.

Pour charger un véhicule sous une limite de poids, chaque branche fixe la présence ou l’absence d’un objet. On préfère cette méthode à une simple règle gloutonne lorsqu’il faut prouver que la valeur totale retenue est maximale.

Pour construire une tournée, une branche fixe une prochaine étape et une borne estime la longueur minimale encore nécessaire. Une heuristique est souvent plus rapide pour obtenir une bonne tournée ; la séparation et évaluation devient utile quand un certificat d’optimalité est exigé.

Dans un solveur, une bonne solution admissible trouvée tôt renforce l’élagage, tandis qu’une relaxation serrée améliore les bornes. Le choix de la prochaine branche agit surtout sur le temps et la mémoire, pas sur l’optimum final si toutes les règles d’exactitude sont respectées.

Énumération exhaustive. Elle évalue chaque solution admissible. La séparation et évaluation reste exacte, mais elle peut supprimer un sous-ensemble entier dès qu’une borne prouve qu’il ne contient rien de meilleur. Dans l’exemple, les choix sans A sont écartés ensemble grâce à la borne de 43 points.

Retour sur trace. Le backtracking coupe typiquement une branche devenue incompatible avec les contraintes. La séparation et évaluation coupe aussi une branche encore admissible lorsqu’elle ne peut plus améliorer l’objectif. Une branche réalisable mais plafonnée à 43 points illustre cette différence.

Métaheuristique. Elle vise généralement une bonne solution sans démontrer qu’aucune meilleure n’existe. La séparation et évaluation fournit ce certificat lorsque l’arbre est fermé avec des bornes valides. L’article Les métaheuristiques présente cette autre famille d’approches.

Borne invalide. Si une borne supérieure sous-estime le gain encore possible, une branche contenant l’optimum peut être coupée. Le symptôme est une relaxation qui exclut des choix pourtant autorisés. Il faut démontrer la validité de la borne avant de l’utiliser.

Égalité avec l’incumbent. Pour trouver une valeur optimale, une branche de borne 56 peut être élaguée lorsque l’incumbent vaut déjà 56. Pour énumérer toutes les solutions optimales, cette branche doit au contraire être conservée, car elle peut contenir une autre solution de même valeur.

Explosion de l’arbre. Des bornes trop lâches ferment peu de branches. La méthode reste exacte, mais peut alors se rapprocher de l’énumération exhaustive et demander un temps ou une mémoire exponentiels dans le pire cas. Il faut renforcer la relaxation, améliorer l’incumbent ou changer la stratégie d’exploration.

Arrondis numériques. Une erreur de calcul près du seuil d’élagage peut inverser une comparaison. Le symptôme est une borne annoncée inférieure à une solution réalisable. Il faut employer des tolérances justifiées ou des bornes certifiées, sans arrondir dans le sens qui rendrait l’élagage incorrect.

Le problème du sac à dos permet d’approfondir le rôle d’une relaxation fractionnaire dans le calcul d’une borne.

Le problème du voyageur de commerce montre comment les bornes servent à comparer des familles entières de tournées.

L’article Les métaheuristiques éclaire le compromis entre recherche rapide d’une bonne solution et preuve d’optimalité.