Academic literature on the topic 'Programmation stochastique multi-étapes prudente'

L’objectif est de développer des modèles mathématiques et des algorithmes qui pourraient permettre de planifier efficacement les activités de production pour des systèmes de production de remanufacturation complexes, en présence d'incertitude. Nous considérons un système de remanufacturation comprenant trois échelons de traitement : le désassemblage, la remise en état et le réassemblage. Nous étudions le problème de la planification dans ce système sur un horizon de planification fini et discret, en présence d'incertitudes quant à la quantité et à la qualité des produits retournés, à la demande des clients et aux différents coûts de production. Nous proposons de modéliser ce problème d'optimisation combinatoire comme un programme entier stochastique à plusieurs étapes et d'utiliser un arbre de scénarios pour représenter l'évolution du processus stochastique dans le temps. Nous nous concentrons sur l'amélioration des performances des algorithmes génériques de branch-and-cut intégrés dans les solveurs de programmation mathématique grâce à l'utilisation d'approches de génération de coupes. Ensuite, afin de résoudre des instances plus grandes de notre problème, nous étudions un deuxième type d'approche de solution basée sur une décomposition du problème original en une série de sous-problèmes liés entre eux par des équations de programmation dynamique. Enfin, nous présentons un travail exploratoire en cours sur la gestion de stock stochastique multi-étapes prudente. Nous étudions ainsi plusieurs façons d'incorporer l'aversion au risque dans le problème (SULS) et montrons comment le SULS prudent peut être reformulé comme un programme linéaire à variables mixtes dans chaque cas
The main purpose of the work presented here is to develop mathematical models and algorithms that may enable industrial managers to efficiently plan production activities for complex remanufacturing production systems under uncertainty. In order to achieve this, we consider a remanufacturing system involving three processing echelons: disassembly, refurbishing and reasembly. We investigate the problem of planning remanufacturing activities in this system over a finite and discrete-time planning horizon when there are uncertainties on the quantity and quality of returned products, on the customers' demand, and on the various production costs. We propose to model this stochastic combinatorial optimization problem as a multi-stage stochastic integer program and to use a scenario tree to represent the evolution of the stochastic input process over time. We first focus on enhancing the performance of the generic branch-and-cut algorithms embedded in mathematical programming solvers through the use of cutting plane generation approaches. Second, in order to solve larger instances of our problem, we investigate a second kind of solution approach based on a decomposition of the original problem into a series of small sub-problems linked together by dynamic programming equations. Finally, we present an on-going exploratory work on risk-averse multi-stage stochastic lot-sizing. We thus study several ways of incorporating risk aversion in the multi-stage stochastic uncapacitated lot-sizing (SULS) problem and show how the risk-averse SULS can be reformulated as a mixed-integer linear program in each case

Dans cette thèse on s'intéresse à la résolution par programmation dynamique de problèmes d'Optimisation Stochastique Multi-étapes (OSM).En première partie, on s'est intéressé à l'approximation des fonctions valeurs d'un problème OSM par des combinaisons dîtes min-plus ou max-plus linéaires de fonctions basiques. Cette approche s'interprète comme l'analogue en algèbre tropicale de modèles paramétriques en programmation dynamique approximatives, notamment étudiés par Bertsekas et Powell.Dans le cadre simplifié des problèmes d'optimisation multi-étapes déterministes, nous introduisons un algorithme, appelé Programmation Dynamique Tropical (PDT), qui construit itérativement des approximations des fonctions valeurs comme combinaisons min-plus ou max-plus linéaires. A chaque itération, une trajectoire d'états est tirée aléatoirement et les états formant cette trajectoire sont appelés points de raffinements. Compte tenu des approximations courantes des fonctions valeurs, PDT calcule alors récursivement en remontant dans le temps, une nouvelle fonction basique à ajouter à la combinaison min-plus ou max-plus linéaire courante. La fonction basique ajoutée à l'approximation au temps t doit vérifier deux conditions de compatibilité : elle doît être exacte au t-ème point de rafinement et valide. PDT évite ainsi de discrétiser l'espace d'état dans sa totalité et tente de s'émanciper du fléau de la dimension.Notre première contribution, dans le cadre de problèmes multi-étapes déterministes, est l'obtention de conditions suffisantes sur la richesse des points de raffinements afin d'assurer presque sûrement la convergence asymptotique des approximations générées vers les fonctions valeurs, en des points d'intérêts.En seconde partie, on a étendu le cadre de l'algorithme PDT aux problèmes stochastiques multi-étapes Lipschitz où les bruits sont finis et indépendants. Dans ce cadre, on génère simultanément des approximations max-plus linéaires et min-plus linéaires des fonctions valeurs. A chaque itération, lors d'une phase vers l'avant, une trajectoire déterministe d'état particulière appelée trajectoire problème-enfant est générée. Ensuite, lors du phase en arrière dans le temps, les approximations courantes sont raffinées en ajoutant des fonctions basiques qui sont exactes et valides.Notre seconde contribution est la preuve que l'écart entre combinaisons linéaires max-plus et min-plus ainsi générées tend vers 0 le long des trajectoires problèmes-enfants. Ce résultat généralise un résultat de Baucke, Downward et Zackeri de 2018 qui prouvait la convergence d'un schéma similaire, introduit par Philpott, de Matos et Zackeri en 2013, dans le cadre de problèmes OSM convexes. Toutefois, la complexité algorithmique de l'extension de PDT présentée dépend fortement de la taille du support des bruits d'un problème OSM donné. En troisième partie, on s'est intéressé à quantifier l'écart entre les valeurs de deux problèmes OSM ne différant que par leur arbre de scénarios. Sous hypothèses de régularités, Pflug et Pichler ont montré en 2012 que la valeur d'OSM est lipschitzienne par rapport à la Distance Imbriquée qu'ils ont introduite. Toutefois le calcul de la Distance Imbriquée nécessite le calcul d'un nombre exponentiel, en la taille de l'horizon, de problèmes de transport optimal. Motivé par le succès de l'algorithme de Sinkhorn pour calculer une relaxation entropique du problème de transport optimal, en troisième contribution nous proposons une relaxation entropique de la Distance Imbriquée que nous illustrons numériquement. En dernière partie, afin de justifier la résolution par programmation dynamique dans des cas plus généraux, des échanges entre intégration et minimisation doivent être justifiés. En quatrième contribution, nous établissons un résultat général d'échange entre intégration et minimisation qui englobe certains résultats usuels
In this thesis, we are interested in the resolution by dynamic programming of Multistage Stochastic optimization Problems (MSP).In the first part, we are interested in the approximation of the value functions of a MSP as min-plus or max-plus linear combinations of basic functions. This approach can be interpreted as the tropical algebra analogue of Approximate Dynamic Programming parametric models, notably studied by Bertsekas and Powell.In the simplified framework of multistage deterministic optimisation problems, we introduce an algorithm, called Tropical Dynamic Programming (TDP), which iteratively constructs approximations of value functions as min-plus or max-plus linear combinations. At each iteration, a trajectory of states is randomly drawn and the states forming this trajectory are called trial points. Based on the current approximations of the value functions, TDP then recursively calculates, by going back in time, a new basic function to be added to the current linear min-plus or max-plus combination. The basic function added to the approximation at time t must verify two compatibility conditions: it must be tight at the t-th trial point and valid. In this way TDP avoids discretising the entire state space and tries to emancipate itself from the curse of dimensionality.Our first contribution, within the framework of deterministic multistage optimization problems, is sufficient conditions on the richness of the trial points in order to ensure almost surely the asymptotic convergence of the generated approximations to the value functions, at points of interest.In the second part, the framework of the TDP algorithm was extended to Lipschitz MSPs where the noises are finite and independent. In this framework, max-plus linear and min-plus linear approximations of the value functions are generated simultaneously. At each iteration, in a forward phase, a particular deterministic trajectory of states called the problem-child trajectory is generated. Then, in the backward phase in time, the common approximations are refined by adding basic functions that are tight and valid.Our second contribution is the proof that the difference between the max-plus and min-plus linear combinations thus generated tends towards 0 along the problem-child trajectories. This result generalises a result from Baucke, Downward and Zackeri in 2018 who proved the convergence of a similar scheme, introduced by Philpott, de Matos and Zackeri in 2013, for convex MSPs. However, the algorithmic complexity of the TDP extension presented is highly dependent on the size of the noise support of a given MSP.In the third part, we are interested in quantifying the difference between the values of two MSPs differing only in their scenario tree. Under assumptions of regularities, Pflug and Pichler showed in 2012 that the value of such MSPs is Lipschitz-continuous with respect to the Nested Distance they introduced. However, the computation of the Nested Distance requires an exponential number (w.r.t. the horizon T) of computation of optimal transport problems.Motivated by the success of Sinkhorn's algorithm for computing entropic relaxation of the optimal transport problem, as a third contribution we propose an entropic relaxation of the Nested Distance which we illustrate numerically.Finally, in order to justify the resolution by dynamic programming in more general cases of MSPs, interchange between integration and minimisation must be justified. In the fourth contribution, we establish a general interchange result between integration and minimization which includes some usual results

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 est vite mise en cause. On considère travailler sur plusieurs périodes de temps et sur un espace d'incertitude discrétisé, en introduisant ainsi les notions des 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 de résolution 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 connus à travers des 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 (DI) est la méthode qui est retenue. Sur les très grandes instances, même les méthodes de décomposition s'avérent longues à converger. Cette thèse est consacrée à de nouvelles mises en œuvre de la DI, 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
In a deterministic setting, data input are considered to be known. However, in real-world applications one may face problems whose parameters are partially or totally uncertain. The approach where one considers a single scenario, which is supposed to represent a mean case, shows quickly its limits. We consider working on 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 which renders 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 clients' 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 (ND)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 ND 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.

Une approche classique pour traiter les problèmes d’optimisation avec incertitude à deux- et multi-étapes est d’utiliser l’analyse par scénario. Pour ce faire, l’incertitude de certaines données du problème est modélisée par vecteurs aléatoires avec des supports finis spécifiques aux étapes. Chacune de ces réalisations représente un scénario. En utilisant des scénarios, il est possible d’étudier des versions plus simples (sous-problèmes) du problème original. Comme technique de décomposition par scénario, l’algorithme de recouvrement progressif est une des méthodes les plus populaires pour résoudre les problèmes de programmation stochastique multi-étapes. Malgré la décomposition complète par scénario, l’efficacité de la méthode du recouvrement progressif est très sensible à certains aspects pratiques, tels que le choix du paramètre de pénalisation et la manipulation du terme quadratique dans la fonction objectif du lagrangien augmenté. Pour le choix du paramètre de pénalisation, nous examinons quelques-unes des méthodes populaires, et nous proposons une nouvelle stratégie adaptive qui vise à mieux suivre le processus de l’algorithme. Des expériences numériques sur des exemples de problèmes stochastiques linéaires multi-étapes suggèrent que la plupart des techniques existantes peuvent présenter une convergence prématurée à une solution sous-optimale ou converger vers la solution optimale, mais avec un taux très lent. En revanche, la nouvelle stratégie paraît robuste et efficace. Elle a convergé vers l’optimalité dans toutes nos expériences et a été la plus rapide dans la plupart des cas. Pour la question de la manipulation du terme quadratique, nous faisons une revue des techniques existantes et nous proposons l’idée de remplacer le terme quadratique par un terme linéaire. Bien que qu’il nous reste encore à tester notre méthode, nous avons l’intuition qu’elle réduira certaines difficultés numériques et théoriques de la méthode de recouvrement progressif.
In the literature of optimization problems under uncertainty a common approach of dealing with two- and multi-stage problems is to use scenario analysis. To do so, the uncertainty of some data in the problem is modeled by stage specific random vectors with finite supports. Each realization is called a scenario. By using scenarios, it is possible to study smaller versions (subproblems) of the underlying problem. As a scenario decomposition technique, the progressive hedging algorithm is one of the most popular methods in multi-stage stochastic programming problems. In spite of full decomposition over scenarios, progressive hedging efficiency is greatly sensitive to some practical aspects, such as the choice of the penalty parameter and handling the quadratic term in the augmented Lagrangian objective function. For the choice of the penalty parameter, we review some of the popular methods, and design a novel adaptive strategy that aims to better follow the algorithm process. Numerical experiments on linear multistage stochastic test problems suggest that most of the existing techniques may exhibit premature convergence to a sub-optimal solution or converge to the optimal solution, but at a very slow rate. In contrast, the new strategy appears to be robust and efficient, converging to optimality in all our experiments and being the fastest in most of them. For the question of handling the quadratic term, we review some existing techniques and we suggest to replace the quadratic term with a linear one. Although this method has yet to be tested, we have the intuition that it will reduce some numerical and theoretical difficulties of progressive hedging in linear problems.