1- Contexte


L'optimisation multi-objectif hiérarchique s'intéresse à des problèmes possédant plusieurs fonctions objectives, classées par priorités décroissantes. Ils peuvent être modélisés de la façon suivante :
"min ( f1(x), ..., fp(x) ) avec x dans D (P)"
où l'ordre utilisé pour le vecteur des objectifs est l'ordre lexicographique.

Un algorithme d'optimisation exact doit procéder en plusieurs étapes pour trouver une solution optimale à l'un de ces problèmes.
Il doit résoudre une séquence de p problèmes d'optimisation Pi, un pour chaque objectif, où l'on a ajouté aux contraintes originales des contraintes d'optimalité : la valeur de chaque objectif précédent est contrainte à être égale à sa valeur optimale.
"min ( f1(x), ..., fp(x) ) avec x dans D et fk(x) = fk* pour tout k < i (Pi)".

2- Tolérance d'optimalité

Tous les solveurs d'optimisation numérique reposent sur des tolérances internes.
Ces tolérances ont plusieurs rôles : éviter des comportements numériques indésirables, combattre des difficultés posées par l'arithmétique en nombres à virgule flottante, ou pour contrôler le temps de calcul.
La tolérance d'optimalité est souvent utilisée dans ce dernier contexte : l'algorithme s'arrête lorsque l'écart entre la meilleure solution et la meilleure borne duale est suffisamment petit.

Un changement de procédure est requis lorsque chaque problème Pi d'un problème multi-objectif hiérarchique est résolu à une tolérance d'optimalité près.

Puisque la valeur optimale n'est plus connue, il faut changer les contraintes d'optimalité.
Plusieurs choix se présentent à nous. Notamment, la valeur des objectifs précédents peut être contrainte supérieurement par
 la borne inférieure à laquelle on ajoute la tolérance
ou par la meilleure solution obtenue pour cet objectif.

3- Quelques différences entre les cas mono- et multi-objectif hiérarchique

Nous étudions l'impact de l'ajout de tolérances sur la résolution du problème, sur les solutions obtenues et sur l'implémentation d'un solveur. Ces phénomènes sont illustrés sur des exemples et des expériences pratiques avec différents solveurs.

L'importance de l'implémentation
Les deux choix d'implémentation des contraintes d'optimalité produisent des sous-problèmes corrects, mais ils présentent tous les deux des comportements inhérents à l'ajout de tolérances.

La majoration par "borne duale + tolérance" donne explicitement la permission au solveur de considérer des solutions sous-optimales pour l'objectif i, qui peuvent alors exploitées par le solveur pour résoudre l'objectif i+1. En pratique, les objectifs sont souvent de nature contraire, ce qui se traduit par des valeurs objectifs fi dans la solution optimale du problème P qui sont moins bonnes que la valeur objectif du problème Pi associé. Cette approche est qualifiée de pessimiste.

La majoration par la valeur de la solution primale est sujette à un autre effet indésirable : la difficulté de résolution des problèmes Pi croît plus fortement avec le nombre d'objectifs déjà résolus, surtout lorsque la meilleure solution courante est obtenue par d'autres approches non exactes.

Interactions avec un solveur parallélisé
Les solveurs industriels exécutent souvent différents algorithms en parallèle. Ce parallélisme peut ajouter de l'incertitude sur les conditions de clôture d'un objectif, voire des difficultés de reproductibilité. Il est ainsi difficile de prévoir quel algorithme fournit la solution ou la borne suffisante pour que l'écart d'optimalité passe sous la tolérance.
Il est donc courant que deux exécutions successives d'un solveur sur un même modèle produise des solutions et des bornes différentes.

Dans un contexte multi-objectif hiérarchique, ces différences sont amplifiées, et il est possible que deux exécutions séparées produisent, pour un même objectif, des intervalles (borne, solution) qui soient disjoints.


Solution optimale : encadrement et distance
Dans le cas mono-objectif, en l'absence de tolérances supplémentaires, la valeur de la solution optimale théorique est toujours située dans l'intervalle de la borne et de la valeur de solution primale. La solution primale ne diffère donc pas de plus de la tolérance de la valeur optimale théorique.

Ces propriétés ne sont plus vraies dans le cas multi-objectif hiérarchique à partir du second objectif: la solution optimale théorique peut être déclarée comme sous-optimale, et l'écart en valeur peut être abritrairement grand.
Nous mettons en évidence une notion de conditionnement entre objectifs pour expliquer ce phénomène.