Génération de scénarios par quantification optimale en dimension élevée

L'optimisation stochastique est une branche de la recherche opérationnelle qui traite de problèmes d'optimisation impliquant des phénomènes aléatoires. Le programme mathématique, défini par une fonction objectif et des contraintes, contient alors une ou plusieurs variables aléatoires et est appelé programme stochastique. Avant de procéder à sa résolution, on doit d'abord modéliser le vecteur aléatoire apparaissant dans le problème. Or, il n'est généralement pas possible de résoudre un programme stochastique pour lequel le support des variables aléatoires est infini, tel que les distributions continues. On doit donc discrétiser la loi probabiliste sur un ensemble fini de réalisations, appelées scénarios, auxquelles on assigne une probabilité. Leur quantité est choisie en fonction du temps de convergence numérique et de la finesse de l'approximation désirés. L'objectif principal de ce mémoire est de développer des méthodes de génération de scénarios permettant d'obtenir des solutions près de l'optimalité pour les programmes stochastiques comprenant des vecteurs aléatoires en haute dimension. Il existe plusieurs méthodes de génération de scénarios, dont la plus courante est l'échantillonnage pur et consiste à tirer les scénarios au hasard à partir de la distribution estimée du vecteur aléatoire. Cependant, les scénarios obtenus par échantillonnage pur sont rarement ceux qui représentent le mieux la loi de probabilités. Dans ce mémoire, nous justifions à l'aide de résultats théoriques et expérimentaux que les scénarios devraient plutôt être générés par la méthode de quantification optimale. Nous montrons ensuite que lorsque le nombre de donnes tend vers l'infini, les problèmes de k-médianes et k-moyennes sont équivalents à la quantification optimale avec les normes L1 et L2 respectivement. Les techniques développées pour générer les scénarios sont donc inspirées d'algorithmes de partitionnement de données. Il n'est pas toujours possible d'estimer avec confiance la distribution d'un vecteur aléatoire à partir d'un ensemble de données. Le cas où la distribution est connue (ou estimable) est donc traité séparément de celui où elle ne l'est pas. Lorsque la distribution est connue et que le problème ne contient qu'une seule variable aléatoire, nous utilisons l'algorithme de Lloyd qui nous permet d'atteindre le minimum global des problèmes de k-moyennes et k-médianes continus. Dans le cas multidimensionnel, nous choisirons plutôt la méthode de quantification vectorielle par apprentissage compétitif (QVAC). La quantification optimale suggéré l'utilisation de la distance induite par la norme L1, puisqu'elle permet d'établir une borne supérieure sur l'erreur de discrétisation du programme stochastique. Afin de quantifier le vecteur aléatoire avec la norme L1, nous adaptons le paramètre de saut de la QVAC, qui est généralement utilisé avec la distance euclidienne. Nous trouvons cependant que la borne supérieure sur l'erreur de discrétisation peut être beaucoup plus grande que l'erreur elle-même. On en déduit que la norme L2 peut également être utilisée pour générer les scénarios et offre une plus grande couverture des événements extrêmes. Lorsque la distribution n'est pas connue, nous utilisons les algorithmes d'échange des centres et de Lloyd (k-médianes et k-moyennes) qui permettent de générer les scénarios directement à partir des données. Dans le dernier chapitre, on analyse entre autres les effets du nombre de scénarios, de la norme utilisée, de la variance et de la dimension du vecteur aléatoire sur nos méthodes de génération de scénarios. On observe sans surprises qu'il est particulièrement difficile d'obtenir des solutions de qualité lorsque la dimension est élevée. Trois méthodes sont donc proposées pour réduire la dimension effective du problème, dont l'analyse par composantes principales et les copules. Parmi celles-ci, on constate cependant que seule l'analyse par composantes principales permet de réduire les coûts de l'optimisation stochastique en dimension élevée. Les scénarios sont testés sur le problème du vendeur de journaux, où la demande suit une loi log-normale ainsi que sur une application réelle à partir d'un ensemble de données historiques lié à la confection d'horaire de personnels. Les solutions de l'optimisation stochastique à partir des méthodes de génération de scénarios proposées ont été comparées à celles obtenues par échantillonnage pur et par l'optimisation déterministe. Pour le problème du vendeur de journaux avec distribution de probabilités connue, des gains substantiels de nos méthodes sont observés pour la quasi-totalité des instances étudiées. Lorsque la distribution n'est pas connue, nos méthodes induisent des erreurs de discrétisation moins de 340 fois plus petites que celles de l'optimisation déterministe avec 100 scénarios. Les erreurs obtenues par les algorithmes d'échange des centres et de Lloyd sont similaires, mais ce dernier reste généralement plus pratique à cause de sa simplicité et sa rapidité d'exécution. Dans le cas du problème de confection d'horaires, nous utilisons toutefois l'algorithme d'échange des centres puisqu'il permet de générer des scénarios de la demande en nombres entiers. Malgré la dimension élevée du problème et les faibles variances, nos méthodes de génération de scénarios permettent tout de même d'obtenir des gains modestes par rapport à l'optimisation déterministe.