3.6 Méthodes de résolution
La résolution des problèmes d'optimisation
combinatoire consiste à trouver la meilleure solution, définie
comme la solution globalement optimale ou un optimum global.La
résolution des problèmes combinatoires est assez délicate
puisque le nombre fini de solutions réalisables croît
généralement avec la taille du problème, ainsi que sa
complexité. Cela a poussé les chercheurs à
développer de nombreuses méthodes de résolution en
recherche opérationnelle. Ces méthodes sont classifiées en
deux grandes classes : Méthodes exactes et Méthodes
approchées.
3.6.1 Méthodes exactes:
Elles garantissent la complétude de la
résolution,mais elles sont souvent limitées au cas des
problèmes de petite taille.Parmi ces méthodes on trouve [14] :
3.6.1.1 Méthode de séparation et
évaluation (Branch and Bound)
L'algorithme par séparation et évaluation,
également appelé selon le terme anglo-saxon "Branch and Bound",
est une méthode générique de résolution de
problèmes d'optimisa-tion, et plus particulièrement
d'optimisation combinatoire ou discrète.
C'est une méthode d'énumération
implicite à l'aide d'une arborescence : toutes les solutions possibles
du problème peuvent être énumérées, mais
l'analyse des propriétés du problème permet
d'éviter l'énumération de larges classes de mauvaises
solutions (des branches sont
3.6 Méthodes de résolution 35
-Page 35-
coupées). Dans un algorithme par séparation et
évaluation, seules les solutions potentiellement bonnes sont donc
énumérées [8].
L'algorithme de branch and bound est basé sur trois
axes principaux : séparation,évaluation,et stratégie de
parcours.
· Séparation : La
séparation consiste à diviser le problème en
sous-problèmes. Ainsi, en résolvant tous les
sous-problèmes et en gardant la meilleure solution trouvée, on
est assuré d'avoir résolu le problème initial. Cela
revient à construire un arbre permettant d'énumérer toutes
les solutions.
L'ensemble de noeuds de l'arbre qu'il reste encore à
parcourir comme étant susceptibles de contenir une solution optimale,
c'est-à-dire encore à diviser, est appelée ensemble des
noeuds actifs.
Son principe : Soient Xr la
solution optimale du programme relaxé (PR) et Xi une variable de base
non entière de Xr telles que : [xi] < xi < [xi] + 1.
(P1)
|
{ (P);
et
xi = [xi]
|
(P2)
|
{ (P);
et
xi = [xi] + 1
|
|
La séparation de (P),selon la variable Xi,consiste
à diviser (P) en deux programmes (P1) et (P2). Désignons par :
R0 : la région ne contenant pas de solutions
entières ;
R1 : la région des solutions réalisables de (P1)
;
R2 : la région des solutions réalisables de
(P2). La séparation consiste à éliminer R0 et à
chercher des solutions entières dans les régions R1 et R2 .
· Évaluation :
L'évaluation permet de réduire l'espace de recherche en
éliminant quelques sous ensembles qui ne contiennent pas la solution
optimale. L'objectif est d'essayer d'évaluer l'intérêt de
l'exploration d'un sous-ensemble de l'arborescence.
Le branch and bound utilise une élimination de branches
dans l'arborescence de recherche de la manière suivante : La recherche
d'une solution de coût minimal, consiste à mémoriser la
solution de plus bas coût rencontré pendant l'exploration, et
à compa-
3.6 Méthodes de résolution 36
-Page 36-
rer le coût de chaque noeud parcouru à celui de
la meilleure solution. Si le coût du noeud considéré est
supérieur au meilleur coût, on arrête l'exploration de la
branche et toutes les solutions de cette branche seront nécessairement
de coût plus élevé que la meilleure solution
déjà trouvée.
Son principe : On utilise en
général des fonctions d'évaluation et des bornes.À
l'étape k,on résout le problème relaxé
(PRk ) associé à (Pk). Pour se faire, deux cas
se présentent:
1. Cas où la solution optimale Xk r est
entière, Z(Xk r ) constitue une borne
inférieure à tous les problème prédécesseurs
au problème (Pr), et en même temps un majorant
à tous les problèmes successeurs au problème
(Pk).
2. Cas où la solution optimale obtenue Xk r
n'est pas entière, on sépare de nouveau le problème
(Pk).
· Stratégie de parcours:
1. Parcours en largeur d'abord: cette
stratégie favorise les sommets les plus proches de la racine en faisant
moins de séparations du problème initial. Elle est moins efficace
que les deux autres stratégies présentées.
2. Parcours en profondeur d'abord: cette
stratégie avantage les sommets les plus éloignés de la
racine (de profondeur la plus élevée) en appliquant plus de
séparations au problème initial. Cette voie mène
rapidement à une solution optimale en économisant la
mémoire.
3. Meilleur parcours d'abord: cette
stratégie consiste à explorer des sous-problèmes
possédant la meilleure borne. Elle permet aussi d'éviter
l'exploration de tous les sous-problèmes qui possèdent une
mauvaise évaluation par rapport à la valeur optimale.
| 
