1.2.2 Méthode de structuration de l'arbre de
recherche
Lorsqu'on construit un arbre de recherche, la structure
proprement dite de celui-ci sera en grande partie déterminée par
les choix concernant les politiques de séparation. Une fois que la
variable sur laquelle on veut brancher a été
déterminée, on doit choisir la politique en ce qui concerne la
séparation du domaine de cette variable. Classiquement, on choisit de
créer un noeud par valeur possible du domaine de la variable. Cela
conduit à des arbres de recherche dont la structure est assez large. On
peut aussi appliquer une politique de séparation binaire : on
crée d'un côté un noeud pour lequel la variable est
fixée à une valeur, de l'autre côté, un noeud pour
lequel la variable est différente de cette valeur. Éxcepté
pour le cas des problèmes à variables binaires, le
problème d'une telle politique réside dans la création
d'un arbre fortement déséquilibré (l'affectation d'une
variable à une valeur a beaucoup plus de conséquences que
l'interdiction de cette valeur). La stratégie equal split
consiste quant à elle à séparer les domaines des
variables en deux sous-domaines de taille égale. L'intérêt
de cette méthode est principalement de créer un arbre
équilibré. Quelle que soit la politique de séparation du
domaine des variables, une fois les noeuds créés, la politique de
choix de l'ordre de traitement des noeuds ainsi créés reste
elle-aussi à déterminer.
1.2.3 Parcours réduit de l'arbre
Dans le cadre de la résolution d'un problème
d'optimisation combinatoire par une méthode exacte, on peut chercher
à obtenir rapidement de bonnes solutions dans un temps limité. Un
des moyens pour y arriver est de transformer la méthode exacte en une
méthode heuristique. Cela passe la plupart du temps par une exploration
incomplète de l'arbre de recherche. Un des moyens les plus simples est
de ne pas traiter l'ensemble des noeuds en attente. Un ordre de priorité
pour le traitement des noeuds en attente est appliqué et on choisit de
ne traiter qu'un certain nombre de noeuds parmi l'ensemble des noeuds. On
restreint donc la recherche à un sous-espace de l'espace original, par
exemple en ne choisissant que les valeurs les plus prometteuses pour chaque
variable lors de l'exploration. Fondamentalement, dans ces méthodes, on
peut considérer que les noeuds non traités sont des noeuds
restant en attente en fin de résolution. Idéalement, on pourrait
donc conserver l'exactitude de la méthode en continuant le traitement
des noeuds jusqu'au bout (au prix de temps de résolution beaucoup plus
important).
Beam Search (Ow et Morton, 1988) est sûrement
l'alternative la plus connue pour tronquer une exploration. Cette approche est
basée sur une exploration en largeur de l'arbre de recherche. On utilise
une fonction heuristique pour estimer l'intérêt de chaque noeud
examiné. A chaque niveau de l'arbre, on garde seulement les w
noeuds les plus prometteurs dans l'ensemble des noeuds ouverts, qui est
l'ensemble de noeuds à
partir desquels la recherche peut continuer. Le terme w
est appelé la profondeur Beam. On voit facilement que plus w
est grand, plus le nombre de noeuds explorés sera important. Ainsi,
lorsqu'on augmente w, on s'approche de la solution qui aurait
été trouvée par une exploration exacte. En règle
générale, l'efficacité de cette approche dépend de
la qualité des bornes inférieures et supérieures. De plus,
tant que w est petit, cette méthode n'est pas
complète.
Limited Discrepancy Search ou LDS , méthode
proposée par Harvey et Ginsberg (1995), dérive d'une recherche en
profondeur classique, mais peut être combinée avec des
règles de sélection de variables et de valeurs. L'idée
principale de cette méthode est de limiter la recherche aux branches qui
ont au plus z déviations (discrepancies). Une
déviation est définie comme une décision contraire par
rapport à une heuristique qui indique le meilleur noeud fils pour chaque
noeud. Une déviation apparaît à chaque fois que le noeud
fils choisi dans une branche n'est pas le meilleur noeud. Par exemple, si l'on
considère les branches avec z = 0 déviation, l'arbre ne
comportera qu'une seule branche : à chaque étape, la recherche
doit suivre la branche qui mène au meilleur noeud. Plus on augmente
z, plus la méthode s'approche d'une résolution exacte.
Néanmoins, cette méthode est par définition assez
dépendante de la qualité de l'heuristique choisie, qui
détermine à chaque noeud la direction à prendre.
La méthode Branch & Greed a
été présentée par Sourd et Chretienne (1999) (voir
par exemple (Néron et al., 2008) pour un article récent
sur cette méthode). Cette méthode consiste à guider un
arbre de recherche incomplet à l'aide d'un algorithme glouton. Comme
pour Beam Search ou pour LDS, on peut paramétrer
l'algorithme grâce à une valeur, notée ici k, afin
que plus ou moins de feuilles soient visitées. L'algorithme parcourt
alors l'arbre de recherche en partant du noeud racine et suit une branche
jusqu'à trouver une feuille. Considérons une itération de
l'algorithme. A l'étape l, la profondeur du noeud courant
noté N, est égale à l. Pour
déterminer le noeud fils de la prochaine étape, l'algorithme
considère l'ensemble des noeuds fils de N dont la profondeur
est égale à l + k. Chacun de ces noeuds
correspond à une solution partielle et, pour chaque solution partielle,
on construit une solution réalisable en utilisant l'algorithme glouton
suivant : on choisit le meilleur noeud fils jusqu'à ce qu'on arrive
à une feuille. Cet algorithme glouton correspond à suivre la
branche qui ne comporte aucune déviation. Notons
Nbest la meilleure solution trouvée durant cette
étape. Le noeud successeur de N dans l'algorithme de Branch
& Greed est le noeud qui permet d'atteindre le noeud Nbest.
La profondeur de ce noeud est donc l + 1 et la procédure de
Branch and Greed continue avec ce noeud. La qualité de l'algorithme
glouton et l'heuristique choisie pour mesurer les déviations
déterminent en grande partie l'efficacité de la
méthode.
Les méthodes décrites ci-dessus
présentent toutes l'intérêt de dépendre d'un seul
paramètre, qui détermine le niveau de complétude de la
résolution. En effet, si ce paramètre est fixé à
une grande valeur, les résolutions seront de type exactes. Ces
méthodes, bien que pouvant s'avérer très efficaces,
présentent néanmoins un défaut principal : leur
réussite est fortement dépendante de l'efficacité des
heuristiques retenues. Dans le cas d'une heuristique peu efficace, les
déviations ne sont pas significatives. On remarque donc que ces
méthodes doivent être adaptées au problème
traité, pour se montrer le plus efficace possible.
| 
