Résolution de grands problèmes stochastiques multi-étapes : Application à un problème de dimensionnement de capacités et de gestion de flux et de stocks

In a deterministic setting, data input are considered to be known. However, in real-world applications we're facing problems whose parameters are partially or totally uncertain. The approach where we consider a single scenario, which is supposed to represent a mean case, shows quickly its limits. We consider working in a discretized uncertainty space spreading over several time periods; we therefore consider scenario trees and introduce the multistage models associated. Problems dimensions rise exponentially with the number of stages that render direct solution methods inappropriate. What has motivated our work, is an industrial application arising in a gas market, concerning more precisely capacity reservation in the context of a contractual agreement that has to hold over a certain time horizon. Spot prices and client demands are considered to be uncertain and are modeled using a scenario tree. The problem structure presents strong similarities with a wide family of problems, where variables are coupling with each other in a very characteristic manner. After a literature survey focusing on (but not limited to) solution methods for multistage models, the Nested Decomposition method has been chosen. Over very large cases, even decomposition methods show their limits; this concerns in principle convergence times. This work is mostly devoted to the development of new procedures inside the Nested Decomposition method, in order to work with larger scenario trees in less time. Other aspects, concerning time reduction over a single iteration are also studied. Comparisons between the classic and the newly presented approaches revealed the superiority of the latter over the former.Dans un monde déterministe, toute donnée d'un problème d'optimisation est censée être connue avec certitude. Dans le monde réel, on est souvent confronté à des cas où certains paramètres sont incertains. La démarche consistant à considérer un seul jeu de paramètres, supposant que ceci représente suffisamment bien la réalité, est vite mise en cause. On considère travailler sur plusieurs périodes temporelles et sur un espace d'incertitude discrétisé, en introduisant ainsi les notions d'arbres de scénarios et des modèles multi-étapes. Les dimensions de ces problèmes augmentent de façon exponentielle avec le nombre de périodes d'étude, rendant les méthodes directes impossibles à appliquer. Le problème qui a motivé ce travail est issu d'une application industrielle réelle et concerne la souscription de contrats dans un marché gazier. Les prix du marché spot, ainsi que la demande clientèle sont considérés incertains, et représentés par un arbre de scénarios. Le modèle qui ressort possède une structure ressemblant à une grande famille de problèmes dynamiques de dimensionnement. A l'issue d'un travail bibliographique, mené particulièrement sur les méthodes de résolution des modèles multi-étapes, la décomposition imbriquée est la méthode qui est retenue. Sur les très grandes instances, même les méthodes de décomposition peuvent s'avérer longues à converger. Cette thèse est consacrée à de nouvelles mises en oeuvre de la décomposition imbriquée, le but étant de pouvoir traiter plus de scénarios en moins de temps. Certains aspects de la méthode sont remis en cause, nous permettant de réduire le nombre d'itérations jusqu'à ce que la convergence soit atteinte. D'autres aspects sont également étudiés dans l'objectif de réduire le temps de calcul passé sur chaque itération séparément. Les démarches proposées sont validées à travers plusieurs séries d'expériences qui mettent en valeur la supériorité de l'approche proposée par rapport à l'approche classique