Academic literature on the topic 'Optimisation multistage'

En optimisation combinatoire classique, étant donné une instance d’un problème, il est demandé de trouver une bonne solution réalisable. Cependant, dans de nombreux cas, les données peuvent évoluer au cours du temps et il est demandé de résoudre une séquence d’instances. Gupta et al. (2014) et Eisenstat et al. (2014) ont proposé un modèle multistage où étant donné un horizon de temps, l’entrée est une séquence d’instances (une pour chaque pas de temps), et l’objectif est de trouver une séquence de solutions (une pour chaque pas de temps) qui atteindrait un compromis entre la qualité des solutions à chaque pas de temps et la stabilité/similarité des solutions pour des pas de temps consécutifs. Dans le Chapitre 1, nous présenterons un aperçu des problèmes d’optimisation prenant en compte des données évolutives. Dans le Chapitre 2, le problème du sac-à-dos est traité dans un contexte offline. La contribution principale est un schéma d’approximation polynomiale (PTAS). Dans le Chapitre 3, le cadre multistage est étudié pour des problèmes multistage dans un contexte online. La contribution principale est l’introduction d’une structure pour ces problèmes avec des bornes presque serrées supérieures et inférieures sur les meilleurs ratios compétitifs de ces modèles. Enfin, dans le Chapitre 4 est présenté une application directe du cadre multistage dans un contexte musical, i.e l’orchestration assistée par ordinateur avec son cible. Nous avons présenté une analyse théorique du problème, en montrant sa NP-difficulté, des résultats d’approximation ainsi que des expérimentations<br>N a classical combinatorial optimization setting, given an instance of a problem one needs to find a good feasible solution. However, in many situations, the data may evolve over time and one has to solve a sequence of instances. Gupta et al. (2014) and Eisenstat et al. (2014) proposed a multistage model where given a time horizon the input is a sequence of instances (one for each time step), and the goal is to find a sequence of solutions (one for each time step) reaching a trade-off between the quality of the solutions in each time step and the stability/similarity of the solutions in consecutive time steps. In Chapter 1 of the thesis, we will present an overview of optimization problems tackling evolving data. Then, in Chapter 2, the multistage knapsack problem is addressed in the offline setting. The main contribution is a polynomial time approximation scheme (PTAS) for the problem in the offline setting. In Chapter 3, the multistage framework is studied for multistage problems in the online setting. The main contribution of this chapter was the introduction of a structure for these problems and almost tight upper and lower bounds on the best-possible competitive ratio for these models. Finally in chapter 4 is presented a direct application of the multistage framework in a musical context i.e. the target-based computed-assisted orchestration problem. Is presented a theoretical analysis of the problem, with NP-hardness and approximation results as well as some experimentations

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<br>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

Among many seawater desalination processes, the multistage flash (MSF) desalination process is a major source of fresh water around the world. The most costly design and operation problem in seawater desalination is due to scale formation and corrosion problems. Fouling factor is one of the many important parameters that affect the operation of MSF processes. This thesis therefore focuses on determining the optimal design and operation strategy of MSF desalinations processes under fouling which will meet variable demand of freshwater. First, a steady state model of MSF is developed based on the basic laws of mass balance, energy balance, and heat transfer equations with supporting correlations for physical properties. gPROMS software is used to develop the model which is validated against the results reported in the literature. The model is then used in further investigations. Based on actual plant data, a simple dynamic fouling factor profile is developed which allows calculation of fouling factor at different time (season of the year). The role of changing brine heater fouling factor with varying seawater temperatures (during the year) on the plant performance and the monthly operating costs for fixed water demand and fixed top brine temperature are then studied. The total monthly operation cost of the process are minimised while the operating parameters such as make up, brine recycle flow rate and steam temperature are optimised. It was found that the seasonal variation in seawater temperature and brine heater fouling factor results in significant variations in the operating parameters and operating costs. The design and operation of the MSF process are optimized in order to meet variable demands of freshwater with changing seawater temperature throughout the day and throughout the year. On the basis of actual data, the neural network (NN) technique has been used to develop a correlation for calculating dynamic freshwater demand/consumption profiles at different times of the day and season. Also, a simple polynomial based dynamic seawater temperature correlation is developed based on actual data. An intermediate storage tank between the plant and the client is considered. The MSF process model developed earlier is coupled with the dynamic model for the storage tank and is incorporated into the optimization framework within gPROMS. Four main seasons are considered in a year and for each season, with variable freshwater demand and seawater temperature, the operating parameters are optimized at discrete time intervals, while minimizing the total daily costs. The intermediate storage tank adds flexible scheduling and maintenance opportunity of individual flash stages and makes it possible to meet variable freshwater demand with varying seawater temperatures without interrupting or fully shutting down the plant at any-time during the day and for any season. Finally, the purity of freshwater coming from MSF desalination plants is very important when the water is used for industrial services such as feed of boiler to produce steam. In this work, for fixed water demand and top brine temperature, the effect of separation efficiency of demister with seasonal variation of seawater temperatures on the final purity of freshwater for both cleaned and fouled demister conditions is studied. It was found that the purity of freshwater is affected by the total number of stages. Also to maintain the purity of freshwater product, comparatively large number of flash stage is required for fouled demister.

Among many seawater desalination processes, the multistage flash (MSF) desalination process is a major source of fresh water around the world. The most costly design and operation problem in seawater desalination is due to scale formation and corrosion problems. Fouling factor is one of the many important parameters that affect the operation of MSF processes. This thesis therefore focuses on determining the optimal design and operation strategy of MSF desalinations processes under fouling which will meet variable demand of freshwater. First, a steady state model of MSF is developed based on the basic laws of mass balance, energy balance, and heat transfer equations with supporting correlations for physical properties. gPROMS software is used to develop the model which is validated against the results reported in the literature. The model is then used in further investigations. Based on actual plant data, a simple dynamic fouling factor profile is developed which allows calculation of fouling factor at different time (season of the year). The role of changing brine heater fouling factor with varying seawater temperatures (during the year) on the plant performance and the monthly operating costs for fixed water demand and fixed top brine temperature are then studied. The total monthly operation cost of the process are minimised while the operating parameters such as make up, brine recycle flow rate and steam temperature are optimised. It was found that the seasonal variation in seawater temperature and brine heater fouling factor results in significant variations in the operating parameters and operating costs. The design and operation of the MSF process are optimized in order to meet variable demands of freshwater with changing seawater temperature throughout the day and throughout the year. On the basis of actual data, the neural network (NN) technique has been used to develop a correlation for calculating dynamic freshwater demand/consumption profiles at different times of the day and season. Also, a simple polynomial based dynamic seawater temperature correlation is developed based on actual data. An intermediate storage tank between the plant and the client is considered. The MSF process model developed earlier is coupled with the dynamic model for the storage tank and is incorporated into the optimization framework within gPROMS. Four main seasons are considered in a year and for each season, with variable freshwater demand and seawater temperature, the operating parameters are optimized at discrete time intervals, while minimizing the total daily costs. The intermediate storage tank adds flexible scheduling and maintenance opportunity of individual flash stages and makes it possible to meet variable freshwater demand with varying seawater temperatures without interrupting or fully shutting down the plant at any-time during the day and for any season. Finally, the purity of freshwater coming from MSF desalination plants is very important when the water is used for industrial services such as feed of boiler to produce steam. In this work, for fixed water demand and top brine temperature, the effect of separation efficiency of demister with seasonal variation of seawater temperatures on the final purity of freshwater for both cleaned and fouled demister conditions is studied. It was found that the purity of freshwater is affected by the total number of stages. Also to maintain the purity of freshwater product, comparatively large number of flash stage is required for fouled demister.

Dans les systèmes manufacturiers de plus en plus complexes, les variations du processus de fabrication et de ses paramètres opératoires ainsi que leurs effets sur l’ensemble du système doivent être maîtrisés, mesurés et contrôlés. Cette thèse propose un cadre d’optimisation pour l’élaboration d’un plan d’inspection optimal qui permet une prise de décision opérationnelle afin d’assurer la satisfaction des objectifs stratégiques (réduction des coûts, amélioration de la qualité, augmentation de la productivité, …). La prise de décision se divise en trois questions : Quoi contrôler ? Comment contrôler ? Quand contrôler ? Le manque d'informations fiables sur les processus de production et plusieurs facteurs environnementaux est devenu un problème important qui impose la prise en compte de certaines incertitudes lors de la planification des inspections. Cette thèse propose plusieurs formulations du problème d’optimisation de la planification du processus d'inspection, dans lesquelles, les paramètres sont incertains et les machines de production sont sujettes aux défaillances. Ce problème est formulé par des modèles de programmation mathématique avec les objectifs : minimiser le coût total de fabrication, maximiser la satisfaction du client, et minimiser le temps de la production totale. En outre, les méthodes Taguchi et Monte Carlo sont appliquées pour faire face aux incertitudes. En raison de la complexité des modèles proposés, les algorithmes de méta-heuristiques sont utilisés pour trouver les solutions optimales<br>Quality inspection in multistage production systems (MPSs) has become an issue and this is because the MPS presents various possibilities for inspection. The problem of finding the best inspection plan is an “inspection planning problem”. The main simultaneous decisions in an inspection planning problem in a MPS are: 1) which quality characteristics need to be inspected, 2) what type of inspection should be performed for the selected quality characteristics, 3) where these inspections should be performed, and 4) how the inspections should be performed. In addition, lack of information about production processes and several environmental factors has become an important issue that imposes a degree of uncertainty to the inspection planning problem. This research provides an optimization framework to plan an inspection process in a MPS, wherein, input parameters are uncertain and inspection tools and production machines are subject to breakdown. This problem is formulated through several mixed-integer mathematical programming models with the objectives of minimizing total manufacturing cost, maximizing customer satisfaction, and minimizing total production time. Furthermore, Taguchi and Monte Carlo methods are applied to cope with the uncertainties. Due to the complexity of the proposed models, meta-heuristic algorithms are employed to find optimal or near-optimal solutions. Finally, this research implements the findings and methods of the inspection planning problem in another application as hub location problem. General and detail concluding remarks are provided for both inspection and hub location problems

Ce travail se rapporte à l'étude de pompes à chaleur à absorption multiétagées, dans le but de développer des nouvelles machines frigorifiques de faible puissance pour la climatisation des bâtiments et utilisant la combustion du gaz naturel comme source de chaleur. Ce type de travail fait l'objet d'une demande de plus en plus importante car il s'avère être une solution de substitution intéressante à l'interdiction récente de production et d'utilisation des composés fluorés tels que les CFC (ChloroFluoroCarbures) et les HCFC (HydroChloroFluoroCarbures). Nous proposons donc dans ce travail, des structures de pompes à chaleur à absorption multiétagées pour frigo pompes qui offrent une excellente voie d'amélioration des performances par rapport aux systèmes simples mono-étages. Dans cette étude, nous nous intéressons plus particulièrement à développer les structures multiétagées en parallèle thermique au niveau du mélangeur, et ce pour une production maximale de froid utile. Ce principe nécessite un mélange qui présente un large domaine de travail (en pression et température). Le mélange utilisé dans cette étude est le couple Nh3/H2O de par ses propriétés et les données thermodynamiques le concernant qui sont assez bien connues. Pour améliorer les performances de ces systèmes, nous distinguons deux grandes voies. La première voie consiste à essayer de profiter de ce besoin de rectification, tandis que la seconde voie cherche à éliminer cette rectification.