Méthodes exactes en optimisation combinatoire

La bonne d'une telle solution conditionne souvent le succès de cette méthode. En effet, avec une solution initiale de bonne qualité, il est plus facile d'augmenter l'efficacité de l'exploration er de diminuer le temps de calcul. Néanmoins, la méthode peut théoriquement fonctionner avec toute solution heuristique réalisable pour le problème étudié.

Elle consiste à décomposer l'univers des solutions en plusieurs sous-ensembles généralement disjoints. Pour que la séparation soit valide il est nécessaire que l'union de ces sous-ensembles couvre toutes les solutions possibles de l'ensemble séparé (ou bien de la branche séparée). Le principe de la séparation est récursif, conduisant ainsi à un arbre de recherche dont l'évolution, pendant le déroulement de l'algorithme, est liée aux sous-ensembles des solutions explorés.

L'évaluation consiste à associer une borne B au problème étudié que l'on calcule pour chaque branche explorée. On parle d'une borne inférieure (respectivement d'une borne supérieure) dans le cas d'une minimisation (respectivement dans le cas d'une maximisation). Cette borne permet d'estimer la performance de la branche évaluée dans le meilleur des cas,.

L'exploration consiste à fixer un protocole donnant l'ordre de visite des différentes branches. On peut choisir par exemple de commencer par explorer les branches les plus prometteuses (celles qui ont la valeur de la borne inférieure la plus petite dans le cas d'une minimisation) en estimant avoir plus de chance de trouver une bonne solution dans cette branche que d'en trouver dans les autres branches. D'autres règles se basant sur les techniques d'exploration des graphes peuvent être également utilisées [Carlier et Chrétienne, 1988]. Au cours de l'exploration et dans un problème de minimisation par exemple, on peut distinguer les cas suivants :

∘ la branche courante S_i est évaluée par B(S_i)≥b₀, avec b₀ la borne supérieure initiale. Dans ce cas, il est inutile d'explorer la branche car dans le meilleur des cas, on va trouver une solution équivalente à la solution heuristique.

∘ la branche courante S_i est évaluée par B(Si)<b₀, dans ce cas, la branche sera séparée et ensuite explorée.

∘ la branche est terminale : c'est à dire, elle correspond à une solution réalisable et par la suite, elle ne peut être séparée. Dans ce cas, si cette solution représente une valeur du critère b₁≥b₀, alors elle sera rejetée. Si b₁<b₀, la solution sera temporairement mémorisée comme étant la meilleure solution et elle remplacera la solution heuristique initiale. Dans ce cas, la valeur de b₀ sera remplacée par b₁. La procédure est résumée dans la figure suivante.