Algorithme

L'algorithme de séparation et évaluation, ou branch and bound, est une méthode utilisée pour résoudre des problèmes d'optimisation. Il divise le problème initial en sous-problèmes plus petits et évalue leur potentiel à contenir la solution optimale, ce qui permet d'éviter une exploration exhaustive de toutes les possibilités.

Avantages et limites

Cette approche est particulièrement efficace pour réduire l'espace de recherche tout en garantissant une solution optimale. Cependant, son principal inconvénient réside dans l'éventuel coût élevé en temps de calcul, surtout pour les problèmes de grande taille, en raison du nombre important de sous-problèmes à générer et à évaluer.

Séparation et évaluation

Phase de séparation

La phase de séparation consiste à diviser le problème principal en sous-problèmes. Ces sous-problèmes correspondent à une partition de l'espace global des solutions possibles. Chaque sous-problème représente un choix ou un ensemble de choix spécifiques liés au problème initial.

Les sous-problèmes seront ensuite explorés, en conservant ceux qui sont prometteurs tout en écartant ceux qui ne peuvent pas mener à une solution optimale. Cela permet de réduire l'espace de recherche tout en maintenant un focus sur les solutions potentiellement intéressantes.

Phase d'évaluation

Une fois les sous-problèmes générés, ils sont évalués pour estimer leur capacité à contenir une solution optimale. Cette évaluation repose sur des bornes supérieures et inférieures calculées grâce à des techniques comme la relaxation continue.

Si une borne inférieure d'un sous-problème dépasse la borne supérieure de la meilleure solution trouvée jusque-là, ce sous-problème est écarté. Cette méthode permet de concentrer les efforts sur les sous-problèmes ayant le potentiel de donner une solution optimale.

Méthode de relaxation continue

La relaxation continue consiste à simplifier un problème combinatoire en relâchant certaines de ses contraintes, rendant ainsi le problème plus facile à résoudre.

Par exemple, dans le problème du sac-à-dos, une relaxation consiste à autoriser à ce que les objets soient fractionnés. Ces solutions approximatives servent à guider la recherche en fournissant des bornes pour chaque sous-problème.

Illustrations avec le problème du voyageur de commerce

Phase de séparation

Le problème est divisé en sous-problèmes en fixant l'ordre de visite des villes partiellement. Par exemple, une branche peut représenter un itinéraire qui commence par la ville A, puis B, puis C. Chaque sous-problème réduit l'espace des solutions possibles en imposant des choix spécifiques pour certaines étapes de l'itinéraire.

Phase d'évaluation

Une relaxation continue calcule une borne inférieure pour chaque sous-problème. Une approche courante consiste à résoudre une version simplifiée du problème, comme un arbre couvrant minimum des villes restantes, pour estimer un coût minimal de parcours. Si cette estimation dépasse le coût du meilleur itinéraire déjà trouvé, le sous-problème est écarté. Seuls les sous-problèmes restant seront résolus.