As I veered away from the stigma of PhD students with incipient baldness, I unknowingly reinforced a second image; that of hermits with questionable hair leading a solitary life. This couldn't be further from the truth. The overall quantity of work required over three years, coupled with the psychological toll the academic work takes, is such that I would have never completed this endeavor without the help of numerous people. While they do not all appear in the manuscript, this space is dedicated to them.

In that spirit, I would like to first offer my most sincere thanks to the reviewers of my thesis, Pr. Frédéric Bonnans and Pr. Ignacio Grossmann, for taking the time to thoroughly read the full manuscript. Particularly, I thank them for helping me clarify certain points I had trouble explaining. I extend these thanks to other members of the jury, starting with Pr. Francesca Maggioni and Pr. Andy Philpott that I had the chance to meet during a winter school in Kvitfjell. I greatly enjoyed the discussions we had on and off the topic of stochastic optimization. A special thank you goes to Dr. Philippe Ricoux who is not only part of this jury, but originated the partnership between the École des Ponts Paristech and TotalEnergies that this thesis is part of. I thank Dr. Anna Robert for her unfailing support throughout the three years and her help in smoothing out the communication between the industrial and the academic worlds.

I cannot express how grateful I am for all the help and guidance my thesis advisor, Pr. Michel De Lara, has provided me with during the PhD. His tough love and caustic humor have gone a long way to stimulate a student that not always had optimal motivation. Among other things, I will remember his everavailability, even across the globe, and his infinite patience to make me a more rigorous person, a more eloquent presenter and a better writer. Then come Pr. Jean-Philippe Chancelier and Dr. Pierre Carpentier, who have provided me with invaluable advice and feedback on my work. Finally, I want to thank Vincent Leclère for convincing me, through our discussions during my Master, to pursue a PhD.

This thesis stems from a partnership between the École des Ponts Paristech and TotalEnergies. When I started, I knew nothing about oil refining and procurement.

It is through the many meetings and discussions I had with Pierre Lutran, Alain Kleinmann and Alireza Tehrani that I got to better understand this incredibly complex world. More precisely, I thank Alireza for welcoming me in his team to teach me the ins and outs of Total's tools, even taking on his free time to help me. I thank Alain and Pierre for carefully reviewing all the work I presented and challenging it with an industrial point of view. Finally, I would like to thank Stephanie Bonnel and Isabelle Simunic, mother figures of the lab, for relieving me of much of the administrative work so that I could focus on my research work. Describing herself as our "greatest fan", I found in Isabelle someone caring and motivating every time I came to see her. I'll remember our numerous discussions about life and career, for she's had the most exceptional one.

Moving to younger and younger researchers, now comes the time of my fellow PhD students. First and foremost, I will be forever grateful to have spent the better part of my PhD in the company of Sébastien, Benoit and Cyrille. Through our shared geekiness we got to share many moments on and off the screen. I owe them a lot for when it came to coping with the loneliness of stay-at-home orders.

More broadly, I want to thank all the PhD candidates and Post-Docs I was fortunate to meet along the way. Among others, Mael, William, Sofiane, Adrien, Inass, Dylan, Clément, Ezechiel, Robert, Olga, Guillaume, Gaspard, Rémi, Nerea, Michel, Hélène, Kexin, Roberta. They made a huge impact on my day-to-day life. I would like to give a special thank you to the next generation of students, Laurent, Edoardo, Alfred and Eloïse, off the top of my head, who almost make me regret I must leave soon. They were here for the last stretch of redaction and unknowingly kept me going thanks to their wits and their laughs. Although I didn't get to spend much time with them, I sincerely hope out paths will cross again.

Last, I would like to mention Adrien and Lucie for their precious friendship over the past years, and for feeding me during the last stages of the redaction. I am proud to call them close friends alongside Sébastien and Juliette.

Although the Cermics has felt like a family for the past three years, it can't substitute to my real family. One of the perks of having a small family is that I only need to address my parents. I will never be able to overstate the way they have supported me, not only during the thesis, but over the past 25 years. They always believed in me, even when I didn't, and have always made sure I could evolve in optimal conditions.

Abstract

The procurement of crude oil for refineries consists in purchasing crude oil and having it delivered on time, to ensure the operation of the refineries. This part of the oil supply chain is essential as the characteristics of the crude oil purchased greatly influences the type of products a refinery will yield. One key particularity of the crude oil procurement is the delay that exists between the moment a crude oil shipment is purchased and the moment it is delivered to a refinery. Each refinery works at a monthly scale. We consider that crude oil arrives at the beginning of each month and then a crude consumption is set for the month. The task of the decision maker is to decide these shipments by making purchase decisions every week of the two preceding months. Up till now, the decision-making of crude procurement relied on a tool simulating the operations of a refinery and the resolution of a static deterministic optimization problem. In this thesis, our main contribution is to take into account financial uncertainty in the decision process.

We start by considering the purchase of crude oil for a single month of operation of a refinery. To that end, we propose a model for the crude oil procurement that takes into account delivery delays. Then, we formulate multistage stochastic optimization problems as well as six purchase policies. The assessment of policies is carried out using a Monte-Carlo simulation as well using historical scenarios. The conclusion is as much about the performances of the policies as it is about possible improvement paths to push the incorporation of uncertainties in purchase policies.

Finally, we propose a procurement problem to manage a refinery during any number of months. We show that this problem can be expressed as a stochastic optimal control problem. Then, we develop a time block decomposition for multistage stochastic optimization problems that enables us to formulate a dynamic programming equation at the scale of the month instead of the week.

Résumé

L'approvisionnement en pétrole brut des raffineries consiste à commander du pétrole afin d'assurer le bon fonctionnement des raffineries. Cette étape est particulièrement importante pour un raffineur, car le type de pétrole acheté conditionne grandement les types de produits que les raffineries pourront produire. La particularité majeure de ce problème vient du délai qui existe entre le moment où un chargement de brut est acheté et le moment où celui-ci arrive à une raffinerie. Chaque raffinerie a un fonctionnement mensuel ; au début de chaque mois, des cargaisons de pétrole brut arrivent au port et sont consommées dans le mois. Ce sont ces cargaisons que l'acheteur doit sélectionner avec une fréquence hebdomadaire, au cours des deux mois précédant la livraison. Jusqu'à présent, la prise de décision d'achat reposait sur un outil modélisant le fonctionnement de la raffinerie et sur la résolution d'un problème statique déterministe. La contribution majeure de cette thèse est la prise en compte d'aléas financiers dans la prise de décision.

Nous étudions d'abord l'approvisionnement d'une raffinerie pour un unique mois de fonctionnement. Pour cela, nous proposons un modèle de l'approvionnement de pétrole brut qui prend en compte les délais de livraison. Ensuite, nous formulons un problème d'optimisation stochastique multi étapes et nous proposons six politiques d'achat permettant de résoudre ce problème. L'évaluation des politiques est faite à la fois par le biais d'une simulation de Monte-Carlo et sur des scénarios historiques. Les conclusions que nous en tirons portent aussi bien sur les performances des politiques que sur des axes de travail pour poursuivre la prise en compte des incertitudes dans l'achat de brut.

Enfin, nous proposons un modèle général d'approvisionnement qui reste au stade théorique. Il s'agit alors de gérer l'approvisionnement en brut d'une raffinerie pour que celle-ci fonctionne durant un nombre quelconque de mois. Nous mettons ce problème sous la forme d'un problème de contrôle optimal stochastique. Ensuite, nous développons une approche par décomposition par blocs temporels qui nous permet d'écrire une équation de programmation dynamique non pas à la semaine, mais au mois.

Chapter 1 Introduction 1.1 Context of the thesis

This thesis started on 2018, November 1 and ended on 2021, December 31. It was the first thesis conducted as part of a partnership between TotalEnergies and the École Nationale des Ponts et Chaussées (ENPC). This partnership was signed in 2018, at the initiative of Philippe Ricoux, and contains two PhD subjects: stochastic optimization for the procurement of crude oil in refineries, and stochastic optimization for petroleum production systems.

The subject of this thesis is the procurement of crude oil, that is, the purchase of oil to ensure the proper operation of a refinery. Consequently, we worked jointly with the "RC" (Refining and Chemistry) department at TotalEnergies. This department, represented by Alireza Tehrani and Alain Kleinmann, is in charge of running the refineries of the group. This broad description encompasses the daily management of the refineries, but also the procurement of resources for the refineries. Other interlocutors included Pierre Lutran and Anna Robert, both part of TotalEnergies's R&D branch.

The thesis took place at the CERMICS laboratory at ENPC, but with frequent meetings between academics and industrials. Initially monthly, these meetings turned weekly when the Covid-19 pandemic broke out. Their object focused on discussions about modeling and numerical results analysis. In parallel to frequent group meetings, I had the occasion to spend time at TotalEnergies's headquarters in order to discuss the more numerical aspects of my work. In particular, I was formed to use some of TotalEnergies's tools.

Subject of the thesis

In 1850, the global crude oil production amounted to 14.000 barrels. The first oil tanker, the "Zoroaster", was constructed several years later, in 1878, by Ludvig Nobel, older brother of Alfred Nobel. This boat navigated the Caspian sea and was able to deliver 240 tons of crude oil in Baku, the world's most important oil trade hub at the time. length: 333 m, capacity: ∼ 250.000 tons Oil has been the cornerstone of the 20th century economic development, and has become central in our society. Yet, it is not an easy-to-work-with natural resource. As shown in Figure 1.3 crude oil is a resource that is difficult to access. Additionally, as exemplified in Figure 1.4, production and consumption happen in different parts of the world as Europe, United-States and China are the largest consumers, with very little production. In parallel, obtaining usable products from crude oil requires a lengthy and complex processing.

The oil supply chain is generally split into the upstream and the downstream supply chains. The upstream supply chain encompasses everything from the extraction of crude oil to the output of finished products by the refineries. Then, the downstream supply chain focuses on distributing products to professional and individual customers. Given the economic importance of crude oil, elements of these supply chains, illustrated in Figure 1.5, have been the subject of optimization works for several decades [START_REF] Lorenz | Retrospective on optimization[END_REF].

First, the oil is extracted from the ground. Investments in oil fields and infrastructures are made over years, and considering multiple future scenarios leads to better, safer decisions [START_REF] Li | A Survey of Optimization Method for Oil-gas Pipeline Network Layout[END_REF][START_REF] Oliveira | Accelerating Benders stochastic decomposition for the optimization under uncertainty of the petroleum product supply chain[END_REF][START_REF] Santoso | A stochastic programming approach for supply chain network design under uncertainty[END_REF][START_REF] Nickel | A multistage stochastic supply network design problem with financial decisions and risk management[END_REF]. Then, crude oil is shipped to a refinery, either through boats or pipelines. Once it arrives, the oil mixes in tanks. This phase is called the blending, or pooling, and is the first part in the scheduling of refinery operations [START_REF] Adhya | A Lagrangian Approach to the Pooling Problem[END_REF][START_REF] Li | Stochastic pooling problem for natural gas production network design and operation under uncertainty[END_REF]. The mix is then processed through a number of units in refineries that separate the components of the crude oil and eventually yield finished products [START_REF] Leiras | Literature review of oil refineries planning under uncertainty[END_REF][START_REF] Alhajri | A nonlinear programming model for refinery planning and optimisation with rigorous process models and product quality specifications[END_REF][START_REF] Karuppiah | Global optimization for scheduling refinery crude oil operations[END_REF]7,[START_REF] Lima | Stochastic programming approach for the optimal tactical planning of the downstream oil supply chain[END_REF]. Most works focus on decisions inside the refinery while taking into account financial variables in the prices of products and of crude oil.

In addition to research work on optimizing the supply chain, crude oil is now treated as a commodity on financial markets. The oil price is closely followed and is the most traded commodity in the world. Because the price of oil is very volatile, oil companies have sought to protect their activity from great price variations and to understand the sources of uncertainty behind these variations [START_REF] Louis H Ederington | Factors influencing oil prices: a survey of the current state of knowledge in the context of the 2007-08 oil price volatility[END_REF]. In that regard, some works [START_REF] Yun | Hedging strategy for crude oil trading and the factors influencing hedging effectiveness[END_REF]9,[START_REF] Ji | Integrated Operational and Financial Hedging for Risk Management in Crude Oil Procurement[END_REF] have been looking for hedging strategies to alleviate the risks posed by the high volatility of crude oil prices. Additional work has been made with the intent to predict, as accurately as possible, the evolution of oil price in the short and long run, either using Markovian models [START_REF] Wai | A Markov switching model of the conditional volatility of crude oil futures prices[END_REF][START_REF] De Souza E Silva | Forecasting oil price trends using wavelets and hidden Markov models[END_REF] Illustration of elements to take into account when purchasing crude oil [START_REF] Jammazi | Crude oil price forecasting: Experimental evidence from wavelet decomposition and neural network modeling[END_REF][START_REF] Wang | Ensemble probabilistic prediction approach for modeling uncertainty in crude oil price[END_REF] or Brownian models [START_REF] Meade | Oil prices -Brownian motion or mean reversion? A study using a one year ahead density forecast criterion[END_REF]. As illustrated in Figure 1.6, procurement sits at the frontier of three domains: crude oil production, refinery operations and finance. It consists in providing refineries the crude oil needed for their operation. Better crude oil purchases mean greater operational margin, either through lowering the purchase costs, or improving the earnings of the refinery. Crude oils have varying physical and chemical properties. These properties impact how one crude mixes with other crudes inside tanks. This also has consequences on the way the oil mix is then refined. Processing the wrong mix can lead to products with the wrong specifications, or can even break the refinery.

While there has been ample academic work on crude oil extraction and refinery operation, procurement of crude oil has remained mostly overlooked. Most articles deal with procurement as the first decision of a two-stage problem [10]: first the decision maker decides what crude oil shipments to buy, then products prices are revealed and the decision maker sets production levels accordingly. In that regard, the model for the refinery is fairly detailed, with controls on production levels as well as settings of some units [START_REF] Kaur | Sustainable stochastic production and procurement problem for resilient supply chain[END_REF]. Carrying oil across the globe takes time. In most cases, shipping times are considered in the design of logistics network [START_REF] Cheng | World-wide cude transportation logistics: a decision support based on simulation and optimization[END_REF] but do not appear in questions asked when buying oil for a refinery. This thesis started from an industrial problem; the TotalEnergies company must take decisions to buy crude oil for refineries. Today, decisions are based on the results of a tool, Grtmps, that models the inner-working of the refinery and on the knowledge of the decision maker. Due to delays that exist between the moment a crude oil shipment is purchased and the moment it is delivered, decision makers have very little hard intel when they make a purchase. This uncertainty applies to financial variables such as the price of crude oil or of the products that are sold by the refinery. Moreover, the decision-maker does not always know what crudes will be in the refinery with the shipment he is considering, and often relies on habits and a "hunch" to predict those elements. Contrary to most work on procurement, our work does not focus on the operations of the refinery, and prefers a "black box" representation with few controls. In return, we focus on the impact shipping delays have on purchasing crude oil. More precisely, we develop multistage stochastic optimization problems in which the decision maker must regularly decide whether he makes purchases ahead of delivery or not.

Thesis overview

The motivation for this thesis was therefore to explore the possibilities opened by incorporating stochastic optimization in the decision process. The manuscript is divided into two parts, arranged in a progression.

Part I Part I deals with the problem closest to the industrial setting initially laid out by TotalEnergies. In this part, we seek to purchase crude oil shipment so as to run the refinery for a single month, hence the name of monthly procurement problem.

Chapter 3 lays the modeling groundwork for the rest of the document. We translate elements from an industrial problem into mathematical notations. In Chapter 3, we identify what are the controls and the sources of uncertainty that we will consider in the rest of Part I.

In Chapter 4, we formulate a first deterministic optimization problem. Then, we provide a stochastic model for uncertainties and formulate a multistage stochastic optimization problem.

In Chapter 5, the stochastic optimization problem is reformulated as a stochastic optimal control problem. As part of the reformulation, we introduce the notion of buffer, a temporary stock in which purchases accumulate until the moment of delivery. Additionally, we present what a policy is in the context of this new problem formulation.

In Chapter 6, we present six policies to tackle the monthly procurement problem. The first one, Expert, puts into equations the method currently used by TotalEnergies. Alongside Expert, two policies -Triplet and MPC-only use a single scenario while the other three -SDP esp , SDP CVaR and Suc-SDP-are based on multiple scenarios. While both SDP esp and SDP CVaR are the standard policies resulting from stochastic dynamic programming, Suc-SDP recomputes new value functions every week.

In Chapter 7, we test and compare the policies presented in Chapter 6. More precisely, policies are tested in two different ways. First, they are (except for Suc-SDP) put through a Monte-Carlo simulation and compared on the basis of their resulting histograms. In parallel, each policy is tested on a selection of historical scenarios and the behavior of each policy is more closely scrutinized.

Part II Part II is devoted to theoretical extensions. While Part I focused on building stochastic optimization problems, bound by technical limitations from TotalEnergies, the problem developed in Part II is a very general procurement problem.

In Chapter 8, we propose a more general model of the procurement of crude oil than that of Chapter 3. We then build a corresponding multistage stochastic procurement problem. That problem has the particularity to feature two concurrent time scales. On the one hand, the decision maker must manage a refinery at the frequency of the month for a long period of time. On the other hand, he must make the decision to purchase, or not, crude oil shipments every week.

In Chapter 9, we first introduce the notion of time blocks and time block state reduction, that is, the ability to express a state variable in only a subset of stages in the problem. We then apply this notion to problems featuring a slow and a fast timescale to write a dynamic programming equation at the slow timescale, that does not require independence assumption on the fast scale noises. The content of this chapter has been submitted as a paper.

Chapter 2 Introduction

Contexte de la thèse

Cette thèse a débuté le 1 er novembre 2018 et a pris fin le 31 décembre 2021. Celle-ci s'inscrit dans un partenariat entre TotalEnergies et l'école des Ponts et Chaussées (ENPC), qui a débuté en 2018 à l'initiative de Philippe Ricoux, et inclue plusieurs sujets de thèse dont : optimisation stochastique pour l'approvisionnement en pétrole brut des raffineries, et optimisation stochastique appliquée aux systèmes de production de pétrole brut.

Cette thèse porte sur l'approvisionnement en pétrole brut, c'est-à-dire l'achat de cargaison de brut de manière à assurer un fonctionnement optimal des raffineries. En conséquence, nous avons grandement collaboré avec la branche "RC" (raffinage et chimie) de TotalEnergies afin de comprendre et de modéliser l'utilisation de brut au sein d'une raffinerie. Cette branche a été représentée par Alireza Tehrani responsable des modèles des raffineries du groupe, et Alain Kleinmann, responsable des opérations d'une raffinerie. En outre, nous avons aussi travaillé en étroite collaboration avec Anna Robert et Pierre Lutran, tous deux pars de la R&D To-talEnergies.

La thèse a pris place au sein du laboratoire CERMICS à l' École des Ponts Paristech, conjointement avec de fréquentes réunions entre académiques et industriels. Initialement mensuelles, ces réunions sont devenues hebdomadaires durant la pandémie de Covis-19. Celles-ci se sont concentrées sur les questions de modélisation et sur les aspects numériques de mon travail. En parallèle de ces rencontres régulières, j'ai aussi pu passer du temps dans les locaux de TotalEnergies pour interagir avec les équipes en charge de l'achat de brut et du maintien des outils utilises. Ces instants m'ont permis de discuter de certains points précis et techniques comme la sélection de données pour les applications numériques.

Sujet de la thèse

En 1850, la production mondiale annuelle de pétrole s'élève à 14.000 barils. Quelques années plus tard, en 1878, le premier pétrolier est bâti. Baptisé "Zoroaster" et construit par Ludvig Nobel, grand frère d'Alfred nobel, il décharge régulièrement jusqu'à 240 tonnes de pétrole brut à Bakou, alors plaque tournante du commerce de pétrole. de l'extraction du pétrole brut, jusqu'à la production de produits finis dans la raffinerie. Ensuite, la chaîne avale porte sur la distribution de ces produits aux différents clients du groupe. Étant donné l'enjeu économique derrière le raffinage de pétrole brut, les éléments de la chaîne de production du pétrole, illustrés en Figure 2.5, ont déjà fait l'objet de nombreux travaux d'optimisation au cours des dernières décennies [START_REF] Lorenz | Retrospective on optimization[END_REF].

Avant toute chose, le pétrole doit être extrait des poches en sous-sol où il se trouve. Les investissements dans des puits de pétrole se font sur de nombreuses années ; prendre en compte plusieurs scénarios aboutit à des décisions moins risquées [START_REF] Li | A Survey of Optimization Method for Oil-gas Pipeline Network Layout[END_REF][START_REF] Oliveira | Accelerating Benders stochastic decomposition for the optimization under uncertainty of the petroleum product supply chain[END_REF][START_REF] Santoso | A stochastic programming approach for supply chain network design under uncertainty[END_REF][START_REF] Nickel | A multistage stochastic supply network design problem with financial decisions and risk management[END_REF]. Une fois sorti de terre, le pétrole est ensuite expédié vers une raffinerie quand il est acheté, cela se fait soit par bateau, soit par pipeline. Une fois arrive à destination, le brut est mélangé dans les cuves de la raffinerie avec les stocks déjà existants. Cette phase de la chaîne de production est la première partie sujette à optimisation dans la planification des opérations d'une raffinerie [START_REF] Adhya | A Lagrangian Approach to the Pooling Problem[END_REF][START_REF] Li | Stochastic pooling problem for natural gas production network design and operation under uncertainty[END_REF]. Le mélange de bruts passe ensuite dans une série d'unités de raffinage qui vont séparer les molécules et les recombiner jusqu'à obtenir divers produits finaux [START_REF] Leiras | Literature review of oil refineries planning under uncertainty[END_REF][START_REF] Alhajri | A nonlinear programming model for refinery planning and optimisation with rigorous process models and product quality specifications[END_REF][START_REF] Karuppiah | Global optimization for scheduling refinery crude oil operations[END_REF]7,[START_REF] Lima | Stochastic programming approach for the optimal tactical planning of the downstream oil supply chain[END_REF]. La plupart des travaux en optimisation portent sur ces deux étapes, qui ont toutes deux lieu à l'intérieur de la raffinerie, en considérant des sources d'incertitude financières comme le prix des produits ainsi que les prix des pétroles bruts.

Parallèlement à des travaux de recherche visant à optimiser le fonctionnement interne de raffineries, l'achat de pétrole brut peut être géré comme l'achat d'un simple actif financier. Étant donné les sommes en jeu, le prix du baril de brut est étroitement surveillé par les équipes financières de groupes pétroliers qui ont cherché à protéger leurs activités des potentielles variations de prix. Le cours du Brent est particulièrement volatile et certains ont tâché de comprendre et de modéliser les sources d'incertitude qui se cachent derrière [START_REF] Louis H Ederington | Factors influencing oil prices: a survey of the current state of knowledge in the context of the 2007-08 oil price volatility[END_REF]. Dans cette optique, certains travaux [START_REF] Yun | Hedging strategy for crude oil trading and the factors influencing hedging effectiveness[END_REF]9,[START_REF] Ji | Integrated Operational and Financial Hedging for Risk Management in Crude Oil Procurement[END_REF] proposent des stratégies de couverture afin de limiter le risque inhérent à un actif hautement volatil. D'autres travaux ont été menés avec l'espoir de prédire, aussi précisément que possible, les futures variations du prix du pétrole a court et long terme, soit en utilisant des modèles Markoviens [START_REF] Wai | A Markov switching model of the conditional volatility of crude oil futures prices[END_REF][START_REF] De Souza E Silva | Forecasting oil price trends using wavelets and hidden Markov models[END_REF], soit en utilisant des réseaux neuronaux [START_REF] Jammazi | Crude oil price forecasting: Experimental evidence from wavelet decomposition and neural network modeling[END_REF][START_REF] Wang | Ensemble probabilistic prediction approach for modeling uncertainty in crude oil price[END_REF], soit des modèles Browniens [START_REF] Meade | Oil prices -Brownian motion or mean reversion? A study using a one year ahead density forecast criterion[END_REF].

Comme l'illustre Figure 2.6, l'approvisionnement en pétrole brut est à la croisée de trois domaines : la production de brut, le pilotage d'une raffinerie, et la finance. En effet, il s'agit d'assurer l'approvisionnement en pétrole brut d'une raffinerie de manière à ce que celle-ci puisse fonctionner dans les meilleures conditions. Améliorer le processus d'achat de brut signifie améliorer la marge dégagée par la raffinerie, que ce soit en diminuant les coûts d'achats ou en augmentant les recettes de la raffinerie. En fonction de leur provenance, les différents pétroles bruts disponibles sur le marché possèdent différentes propriétés physiques et chimiques. Ces caractéristiques impactent non seulement comment différents bruts se mélangent, mais aussi la manière dont le pétrole peut être raffiné. En fonction du mix du mélange de brut qui est traite, le cocktail de produits finis qui sera obtenu pourra varier. En outre, traiter un mauvais mélange peut générer des produits aux mauvaises spécifications, ou bien même endommager les composants de la raffinerie.

Alors que la littérature portant sur l'extraction de pétrole brut ainsi que sur le pilotage d'une raffinerie est relativement développée, le sujet de l'approvisionnement reste largement ignore. La majorité des articles traitent l'achat de brut comme la première décision d'un problème d'optimisation stochastique à deux étapes ; tout d'abord, un ensemble de bruts est choisi puis mélange, ensuite, les prix des produits finis sont révélés et le pilotage de la raffinerie est décidé. Dans la plupart des cas, les délais de livraison sont pris en compte dans l'élaboration d'un réseau logistique.

Cette thèse a débuté avec un problème industriel ; celui qu'un raffineur, To-talEnergies, rencontre lorsqu'il doit se fournir en pétrole brut. Aujourd'hui, les décisions d'achats sont basées sur un outil, Grtmps, qui modélise le fonctionnement interne d'une raffinerie, ainsi que le savoir accumulé par la personne responsable pour chaque raffinerie. En raison des délais de plusieurs semaines qui existent entre le moment où la commande d'un chargement de brut est passée, et le moment où cette commande est livrée, le décideur ne possède que peu d'information au moment d'effectuer un achat. Cette incertitude concerne aussi bien des variables financières comme les prix des produits et des bruts, que des What crudes to buy?

Apreçu du contenu de la thèse

La raison d'être de cette thèse est l'exploration des possibilités offertes par la prise en compte de sources d'incertitude dans le processus d'achat de pétrole brut pour une raffinerie. Le manuscrit de la thèse est subdivisé en deux parties selon la difficulté du problème abordé.

Part I La Part I traite du problème le plus proche du problème industriel initial présenté par TotalEnergies. Dans cette partie, nous cherchons à acheter des cargaisons de pétrole brut de manière à faire fonctionner la raffinerie pendant un mois, d'où le nom de problème d'approvisionnement mensuel. Chapter 3 propose les bases de modélisation pour la suite du document. Nous traduisons les éléments du problème industriel en des notations mathématiques. Dans Chapter 3, nous identifions quels sont les contrôles ainsi que les sources d'aléa avec lesquelles nous travaillerons dans le reste de la Part I.

Dans Chapter 4, nous formulons un premier problème d'optimisation déterministe . Ensuite, nous proposons un modèle pour les aléas identifies précédemment, et formulons ensuite un problème d'optimisation stochastique.

Dans Chapter 5, le problème d'optimisation stochastique multiétapes est reformule en un problème de contrôle optimal. Cela passe par l'introduction de la notion de stock temporaire (buffer) dans lequel s'accumulent tous les achats en attente de leur livraison. Enfin, nous présentons ce à quoi ressemblerait une politique d'achat dans ce contexte.

Dans Chapter 6, nous présentons six politiques d'achat de pétrole brut. La première, Expert, retranscrit aussi fidèlement que possible le processus d'achat tel qu'implémenté par TotalEnergies. En plus d'Expert, deux autre politiques -Triplet et MPC-ne basent leurs décisions que sur une unique vision du futur.

Les trois politiques restantes -SDP esp , SDP CVaR et Suc-SDP-se basent sur de multiples scénarios. SDP esp et SDP CVaR sont les implémentations des politiques résultantes d'une utilisation standard de la programmation dynamique stochastique. En revanche, Suc-SDP met à profit le temps disponible entre aléa et décision pour générer de nouvelles projection du futur et recalculer les fonctions valeurs a chaque pas de temps.

Enfin, dans Chapter 7, nous testons chacune des six politiques élaborées dans Chapter 6 et les comparons. PLus précisément, les politiques sont évaluées de deux manières l la première est une simulation de Monte-Carlo qui nous permet de comparer les politiques au travers d'histogrammes ; la seconde est la simulation de chaque politique d'achat sur une poignée de scénarios historiques. Nous pouvons alors étudier plus en détail le comportement de chaque politique.

Part II Part II doit être vu comme une extension théorique. Alors que Part I s'est focalise sur la construction d'un problème d'optimisation stochastique respectant certaines contraintes industrielles posées par TotalEnergies, le problème développe dans Part II est un problème d'approvisionnement générique.

Dans Chapter 8, nous proposons un modèle d'approvisionnement en pétrole brut plus général que celui construit dans Chapter 3. Nous formulons ensuite un nouveau problème d'optimisation stochastique correspondant, qui a la particularité de posséder deux échelles de temps imbriquées. D'une part, la raffinerie est pilotée à l'échelle du mois et à long terme ; d'autre part, les achats de pétrole sont faits chaque semaine avec un horizon d'au plus deux mois.

Dans Chapter 9, nous introduisons tout d'abord la notion de bloc temporel (time block) et de réduction de l'état par bloc, c'est-à-dire la possibilité de n'exprimer une variable d'état qu'en certains instants. Cette notion est alors appliquée à une catégorie de problèmes d'optimisation exhibant deux échelles de temps, une rapide et une lente. Nous arrivons alors à écrire un état et des équations de programmation dynamique a l'échelle lente sans pour autant nécessiter d'hypothèse d'indépendance des bruits à l'échelle rapide au sein de chaque pas de temps lent. Le contenu de ce chapitre fait l'objet d'un papier.

Part I

Monthly procurement problem

In this Part I, we explore the monthly crude oil procurement of a refinery. The term monthly, here, refers to the duration of the production in the refinery. We seek to purchase oil so as to run the refinery for the duration of a month.

In the monthly crude oil procurement, the decision maker seeks to buy crude oil to run the refinery for a duration of a single month. For this, he needs to purchase crude oil up to two months ahead of time. As a result, counting the purchases and the consumption, the monthly crude oil procurement spans three months.

Chapter 3 lays the modeling groundwork for the rest of the thesis. We translate elements of a purely industrial problem into mathematical notations. Consequently, we identify what are the controls and the sources of uncertainty we will consider in the rest of Part I. Then, in Chapter 4, we formulate a first deterministic optimization problem and we put into equations the method currently used by TotalEnergies. Then, we provide a stochastic model and formulate a multistage stochastic optimization problem. That problem is then reformulated as a stochastic optimal control problem in Chapter 5 where we introduce the notion of buffer, a temporary stock in which purchases accumulate until the moment of delivery. In Chapter 6, we present five additional policies to tackle the monthly procurement problem. These policies are then compared in Chapter 7 through a Monte-Carlo simulation and historical scenarios.

Chapter 3

Modeling elements for the procurement problem

Introduction

This Chapter 3 provides the basic modelling tools for the monthly procurement problem.

In §3. [START_REF] Alhajri | A nonlinear programming model for refinery planning and optimisation with rigorous process models and product quality specifications[END_REF] we describe what the procurement of crude oil consists in from the point of view of the decision maker and develop several of its specificities. Then, in §3.3, we introduce mathematical notations to formalize the elements presented in §3.2. We also go into more details to identify what are the decisions and sources of uncertainty in the industrial problem.

Monthly procurement description

We provide an overview of what the monthly crude oil procurement consists in, from the point of view of the decision maker. With that intent, we present, in Figure 3.1, an example of monthly procurement problem. Monthly refers here to M 3 , the month we intend to run the refinery for. The role of the decision maker is therefore to purchase crude oil ahead of the month M 3 , that is, during the months M 1 and M 2 (8 purchase weeks), so as to have it delivered at the beginning of the consumption month M 3 . In doing so, the decision maker is faced with several difficulties: different crude oil characteristics, delivery delays, and uncertainties.

Crude oil characteristics

As crude oil is traded on a global market, many crudes with different names exist. Total regularly considers over 180 different crudes for the refineries it operates. All these crudes have different chemical and physical properties, so that processing them will yield different results in terms of products. In fact, some crudes may even be impossible to process together as they would over/under load certain parts of the refinery. In Figure 3.2, we give an example of varying physical and chemical properties for different crudes. The Figure 3.4 highlights how the refinery splits components depending on the length of their carbonated chains. As a consequence, two crudes with different concentrations of long chains (for instance with a heavy crude and a light one), will yield different quantities of products.

Delivery delays

The supply chain to deliver crude oil to a refinery is lengthy. Crude oil first needs to be extracted and loaded onto a tanker to then be shipped to the target refinery, for example Donges as represented in Figure 3.5.

Another consequence of having a global crude oil market is that the shipping times vary considerably. For the Donges refinery, the delay between an order and its delivery is around 3 weeks for the crudes from the North Sea, such as Ekofisk. It is around 9 weeks for West African crudes like Cabinda, and 6-7 weeks for Eastern crudes like Azeri. In Figure 3.6, we display the location of those three oil fields.

From the point of view of the decision maker, who has a precise arrival date in mind, not all crudes are available for purchase at the same time.

Uncertainties

The role of the decision maker is to purchase crude oil. As explained in §3.2.1, the purchase of different crudes will lead to different quantities of products at the output of the refinery. Additionally, due to the varying shipping delays, purchase decisions are taken successively in time. As exemplified in Figure 3.7, the price of crude oil is ever-changing. Put simply, the decision maker, that we will refer to as "he", knows the prices of crudes at the moment of purchase, but not the prices tomorrow. The uncertainty he is faced with is a financial uncertainty, both in the prices of the crude oils, and in the product prices. As mentioned in §3.2.2, crudes are purchased multiple weeks in advance, the decision maker has no way to know, in advance, the prices of the products during the production.

Monthly crude oil procurement example

In light of the elements introduced in §3.2.1, §3.2.2 and §3.2.3, we present in Figure 3.8 an example of monthly procurement problem. In Figure 3.8, the decision maker is faced, each week of M 1 and M 2 , with a handful of crudes that are available to purchase. Each week, he must decide whether to buy oil available on the moment, or wait for the next week, without knowing exactly how the prices will evolve as illustrated in Figure 3 In the following section, we come back on every element introduced in the subsections §3.2.1 to §3.2.4 and we introduce mathematical notations and modeling element to precise this broad description of the problem.

Procurement mathematical modeling

In this section §3.3, we take the general elements presented in §3.2 and add mathematical notation. These notations are the building blocks of the crude oil procurement model that we use in Part I. First, in §3.3.1, we go into details explaining the events, the decisions and the sources of uncertainty that affect the procurement of crude oil up to the delivery of crude oil in a refinery. Then, in §3.3.2, we identify the controls and the sources of uncertainty that affect crude oil processing and product sales.

Upstream procurement

This subsection §3.3.1 strictly concerns the procurement of crude oil. First, in S3.3.1.1 we justify the discretization of time at the scale of the week. Then, in §3.3.1.2, we present the model used for crude cargos. In §3.3.1.3, we present the sources of uncertainty affecting the upstream procurement and precise those that are in the scope of this work.

Timeline representation

In Table 3.1, we summarize the elements that we are going to introduce in relation to time. We denote by M the finite chain of months for which we need to manage the procurement, fitted with the following total order:

M = {M 1 , M 2 , M 3 } set of
m = M 1 ≺ M 2 ≺ M 3 = m . (3.1)
We call chain, a totally ordered finite set and we denote m + (resp. m -) the successor (resp. predecessor) of m ∈ M. Similarly to months, weeks have the structure of a finite chain:

w = 1 ≺ 2 ≺ 3 ≺ 4 = w . (3.2)
Additionally, we denote by the couple (m, w) ∈ M × W a specific week w of a month m. We create a lexicographic order on M × W by defining the successor of (m, w) by

(m, w) + = (m, w + ) if w ≺ w , (m + , w) if w = w . (3.3)
We then build the set

T = {(m, w) | m ∈ {M 1 , M 2 }, w ∈ W} , (3.4)
of weeks during which purchases can be made with the order induced by (3.3), T is a chain. For instance, the two months M 1 and M 2 will have the chronology presented in Figure 3.10.

M 1 (M 1 , 1) week1 (M 1 , 2) week2 (M 1 , 3) week3 (M 1 , 4) week4 M 2 (M 2 , 1) week5 (M 2 , 2) week6 (M 2 , 3) week7 (M 2 , 4) week8 M 3 (M 3 , 1)
Figure 3.10: Time discretization scheme; everything that happens during week w is summed up in the point w which starts the week

The reason behind such a discretization of time is the way Total operates. While refineries run 24/7 and the crude oil market fluctuates continuously, the purchase decisions and the oil deliveries are periodic. Once every week, the decision maker is provided with a projection of the market, and he must take a decision within 72 hours, hence the weekly discretization of the problem.

By adopting this weekly discretization, we summarize all the actions during a week in one point at the start of it, as illustrated in Figure 3.10. This contraction is also valid for months; if a decision (or uncertainty) affects the whole month m, it will be considered to have been taken at the beginning of m.

At the weekly scale, all the refinery does is purchase crude oil. The refining of crude oil, although it is a continuous operation, is decided once a month.

Crude oil logistics

In Table 3.2, we summarize the elements that we are going to introduce regarding crude oil logistics. Table 3.2: Notations for order/shipping chronology TotalEnergies's historical expertise as an oil company is to buy crude oil and process it. The company does not own tankers to transport crude oil; instead, this task is left to third party actors. This configuration plus physical limitations considerably constrain the decisions TotalEnergies can make. We denote by

c ∈ C , (3.5a)
a crude c among the set C of crudes on the market. We usually refer to crudes using a three letters code, for instance: WTI (Western Texas Intermediate), EKO (Ekofisk), NVY (Novigrad). Additionally, depending on their characteristics, crudes can be divided into families. We will denote

C = l∈L C l (3.5b)
the partitioning of crudes in families, where L is the set of existing families. In the example presented in Figure 3.12, we have

C 1 = {B1, B2, B3, B4, B5} , (3.5c
) C 2 = {H1, H2, H3, H4, H5, H6} , (3.5d)

C 3 = {L1, L2, L3, L4, L5, L6, L7, L8} , (3.5e) C = C 1 ∪ C 2 ∪ C 3 .
(3.5f)

In this example, 1 is the family of balanced crudes, while 2 is the family of heavy crudes and 3 is the family of light crudes.

Shipping chronology. As presented in §3.2.2, delivery delays vary for each crude. We denote by ∆ c ∈ 1, 8 = {1, 2, 3, 4, 5, 6, 7, 8} ,

the shipping delay, in weeks, for the crude c. This delay corresponds to the number of weeks between the purchase week and the beginning of the month M 3 .

Order week (m, 1) -∆ c

Order delay

Delivery month (m, 1) When we write (m, 1) -∆ c , the couple (m, w) is identified with its order in the chain M × W fitted with the total order defined in (3.3). Looking back at the example in Figure 3.8, we have ∆ H1 = 8 and ∆ B4 = 4. With a delivery set for the month M 3 , Cabinda (H1) is available for purchase in week (M 3 , 1) -8 → (M 1 , 1) while Oseberg (B4) is available in week (M 3 , 1) -4 → (M 2 , 1). Looking back at the example in Figure 3.8, we have ∆ H1 = 8 and ∆ B4 = 4. With a delivery set for the month M 3 , (H1) is available for purchase in week (M 3 , 1) -8 → (M 1 , 1) while (B4) is available in week (M 3 , 1) -4 → (M 2 , 1).

Tankers reduce flexibility. Shipping crude oil across the globe is almost exclusively done using tankers. Although oil is contained in several tanks inside a ship, in practice, a boat only transports one type of oil. Those boats have somewhat standard sizes, split into classes. Tanker categories are summarized in Table 3 As a consequence, we consider that the volumes of crude that can be purchased belong to a finite set G = {7.5.10 3 , 4.5.10 5 , 6.10 5 , 8.10 5 , 1.5.10 6 , 2.4.10 6 } ,

and most often, a crude is only available in a single cargo size. Sizes vary dramatically and only the largest tankers, Very Large Crude Carriers and Ultra Large Carriers, are big enough to deliver crude oil to multiple refineries but are too large to go through the Suez canal. This situation constitutes one of the reasons why we only consider a single refinery in this Part I. In practice, refineries are almost independent from one another and, here, we consider that they are entirely independent.

Upstream procurement decisions. In the procurement of crude oil, the main decision is to buy oil. We denote by

b c (m,w) ∈ U c (m,w) ⊆ G ⊆ R + , (3.8a)
the quantity that is effectively purchased. Due to the modeling choice presented in §3.3.1.2, G is a finite set that represents the existing cargo volumes. For ease of use, we introduce the notation

b (m,w) = (b c (m,w) ) c∈C ∈ U sf (m,w) ⊆ G |C| , (3.8b) U sf (m,w) = c∈C U c (m,w) ⊂ G |C| , (3.8c)
where b (m,w) in (3.8b) is the vector of all crudes purchased in week (m, w) for the month M 3 .

We now represent in Figure 3.12 how the decisions appear on the timeline of the monthly procurement problem. In Table 3.4, we summarize the elements that we are going to introduce in relation to crude oil trading

w c (m,w)
∈ R value of the premium of the crude c (in $/bbl) at the beginning of the week (m, w)

rf (m,w) ∈ R reference quotation (in $/bbl) in week (m, w) Ω (m,w)
sum paid to purchase crude oil in (m, w) with the premium w t Table 3.4: Price notations related to oil trading Crude oil is a primary resource and is traded globally in Future Exchanges (NYMEX, ICE, NADEX). Future contracts are buy/sell promises of a certain amount of goods at a determined date and price. The full cost of a crude oil is not yet known at the moment it is purchased. In the case of oil, the general structure of cost encompasses: premium The premium is negotiated between the producer and the buyer at the moment of purchase. It corresponds to the relative value of a crude compared to the Brent, the reference crude commonly used.

reference The reference quotation is the mean value of the reference crude Brent over 5 work days around the date the crude oil is loaded into the tanker (-2, -1, 0, +1, +2).

freight The freight is the cost, per barrel to ship the crude oil from the producer to the refinery.

insurance As with any cargo, the insurance cost is fixed at the moment the oil is loaded onto the tanker.

This price structure is displayed in Figure 3.13. In this thesis, we focus on the uncertainty in the premium of crude oil. We denote by

w c (m,w) ∈ R , (3.9)
the premium of the crude c at the beginning of the week (m, w) and by

w (m,w) = (w c (m,w) ) c∈|C| ∈ R |C| , (3.10)
the vector of all premiums at the beginning of week (m, w) where C is the set of crudes introduced in §3.3.1.2.

According to Total, variations of the reference crude price, of the shipping, and of the insurance tend to affect all crudes equally. Therefore, the financial department of the company is able to edge the risk regarding these three components. In the rest of the thesis, we therefore treat the reference, the shipping cost and the insurance as deterministic and parameters of the problem. We therefore denote by Additionally, we denote by

Ω c (m,w) : R + × R -→ R (b c , w c ) -→ Ω c (m,w) (b c , w c ) , (3.11a
Ω (m,w) : R |C| + × R |C| -→ R , (b, w) -→ Ω (m,w) (b, w) = C∈C Ω c (m,w) (b c , w c ) , (3.11c)

Refinery processing

In this §3.3.2, we describe and introduce notations for what happens once crude oil reaches the refinery. While the procurement of crude oil per se is finished the moment crude oil is delivered, the operations of the refinery require to be modeled to some extent in order to make the right purchase decisions.

Receiving oil in the refinery

In Table 3.5 we summarize the elements that we are going to introduce that are relative to the reception of crude oil inside the refinery.

S

S = {(s c ) c∈C | 0 ≤ s c ≤ vol c max , ∀c ∈ C} , (3.12b)
where vol c max simply denotes the maximum of crude c the refinery can hold in stock.

The delivery of crude oil must also respect certain constraints that we denote by

D m ⊂ G |C| . (3.12c)
This constraint represent limits of the refinery to receive crude oil from tankers. Once crude oil as been delivered to the refinery at the beginning of the month M 3 , the refinery processes it to yield products. We denote by

p ∈ P , (3.13)
a finished product among the set P of products that can be sold by the refinery every month. Each product p is subsequently sold at a certain price we denote by

p p m ∈ R + . (3.14)
We denote by

p m = (p p m ) p∈P ∈ R |P| + , (3.15)
the vector of product prices for the month m.

In this Part I, the refinery runs during a single month. In an attempt to simplify the notations, we ignore any control on crude consumption and represent the economic function of the refinery for the month M 3 by the function

Ψ M 3 : R |C| + × R |C| + × R |P| + -→ R (3.16) s M 3 , (M 2 ,4) (m,w)=(M 1 ,1) b (m,w) , p M 3 -→ Ψ M 3 s M 3 , (M 2 ,4) (m,w)=(M 1 ,1)
b (m,w) , p M 3 .

Conclusion

In Chapter 3, we broadly presented the monthly crude oil procurement problem in §3.2 and then introduced modeling elements in §3.3. We split the procurement problem in two phases: the first one, presented in §3.3.1, covered the journey of crude oil from the producer to the refinery; the second, in §3.3.2, focused on the processing of the crude oil inside the refinery. In either case, the first step towards modeling was to describe each process and identify the relevant elements to represent. Once this achieved, we were able to identify decision variables as well as to pinpoint sources of uncertainty.

In the next Chapter 4, we will write optimization problems using the elements presented in this Chapter 3.

Chapter 4

Monthly procurement optimization problem formulation 4.1 Introduction

In this Chapter 4, we formulate a series of stochastic optimization problems to represent the decision problem outlined in Chapter 3.

First, in §4.2, we start by expressing an economic function and then formulate a first deterministic optimization problem. Then, in §4.3, we introduce a stochastic model for the sources of uncertainty presented in Chapter 3. This allows us to transform the deterministic problem from §4.2 into a multistage stochastic optimization problem.

Deterministic optimization problem formulation

In this section, we start by building an objective function from the elements introduced in §3.3.1.3 and §3.3.2.2. We then use this function to write a first deterministic optimization problem.

Economic function

We recall the setting of the monthly procurement problem in Figure 4.1.

As presented in §3.3.1, we only represent the crudes premiums w (m,w) as well as the product prices p M 3 . These are the two sources of financial uncertainty we have retained. Since other financial parameters are deterministic, they are hidden in the cost functions introduced in (3.11c) and (3.16). Therefore, the decision maker:

b (M 1 ,1) b (M 1 ,2) b (M 1 ,3) b (M 1 ,4) b (M 2 ,1) b (M 2 ,2) b (M 2 ,3) b (M 2 ,4) M1 1 2 3 4 M2 1 2 3 4 M3 1 2 3 4 M4 1 c stock de la raffinerie
pays Ω t (b t , w t ) every week from (M 1 , 1) to (M 2 , 4), pays Ψ M 3 s M 3 , (M 2 ,4) t=(M 1 ,1) b t , p M 3 during the month M 3 (productions costs - earnings)
From these two functions, we create a third one

Ξ M 3 s M 3 , (b t ) t∈T , (w t ) t∈T , p M 3 = (M 2 ,4) t=(M 1 ,1) Ω t (b t , w t ) + Ψ M 3 s M 3 , (M 2 ,4) t=(M 1 ,1) b t , p M 3 , (4.1
) that represents the overall cost of handling the procurement of oil for one month, with consumption. We use Ξ M 3 as the economic function for the monthly procurement problem.

Deterministic optimization problem formulation

Using (4.1) as the objective function, we formulate a first deterministic optimization problem min

{b t } t∈T Ξ M 3 s M 3 , (b t ) t∈T , (w t ) t∈T , p M 3 (4.2a) s.t b t ∈ B t ∀t ∈ T , (4.2b) t∈T b t ∈ D M 3 , (4.2c)
where (4.2c) represents that only certain cargos combinations can be purchased for the target month M 3 as introduced with (3.12c). For instance, this constraint might put a cap on the total volume of oil that can be delivered to the refinery at the beginning of M 3 . In the case of this problem, the constraint (4.2c) represents three things:

exactly three (3) shipment must be delivered for M 3 , no more than one shipment must contain heavy crude, no more than one shipment must contain light crude.

In Problem (4.2), we seek the succession of purchases (b * t ) t∈T that maximizes the margin of the refinery for the month M 3 , in an anticipative setting.

Stochastic optimization problem formulation

In Problem (4.2), the variables {w t } t∈T , p and s that were identified in Chapter 3 as sources of uncertainty, are parameters of the problem. Therefore, the optimization in problem (4.2) takes place as if the future was known in advance. In §4.3.1, we propose a stochastic model for these sources of uncertainty. Then, in §4.3.2, we use that model to build a multistage stochastic version of the Problem (4.2).

Stochastic models

In this section we will build a stochastic model for the sources of uncertainty identified in Chapter 3. There are three sources: the premiums of crudes, the stock at the beginning of the month M 3 , and the product prices during that month. After discussion with engineers from TotalEnergies, we convened to model these uncertaunties as follow: crude premiums (w) are modeled by a number of hidden Markov chains, one for each category of crude l ∈ L, the stock s M 3 is modeled as a discrete, independent, random variable that can only take a finite number of vales, the product prices vector p M 3 is also modeled as a discrete, independent, random variable.

We now build the probability space (Ω, F, P) that corresponds to this model for uncertainties.

Hidden state :

n (M1,1) n (M1,2) n (M1,3) • • • n (M2,4)
Observations (premiums) :

w (M1,1) w (M1,2) w (M1,3) • • • w (M2,4) M F M F M F M F Figure 4.

2: Illustration of the hidden markov chain modeling the crude oil premiums

We decided to model premiums as a hidden Markov chain. Therefore, there exists an underlying state n t that behaves like a Markov chain of transition matrix M , and whose premiums p t is an observation of, as illustrated in Figure 4.2.

As explained in Chapter 3, crudes are divided into families, with L the set families. We consider that the evolution of prices are independent family by family. Therefore, we split the hidden state n t according to the families

n t = (n l t ) l∈L , (4.3a)
and the crude premiums depend only on the state of their corresponding family

F (w t | n t ) = l∈L F (w c t ) c∈C l | n l t . (4.3b)
Subsequently, we denote by (Ω cd , F cd , P cd ) the canonical probability space for a hidden Markov chain of transition matrix M and observation law F with

Ω cd = R |C|×8 , (4.4a) ω = (w (M 1 ,1) , w (M 1 ,2) , w (M 1 ,3) , w (M 1 ,4) , w (M 2 ,1) , w (M 2 ,2) , w (M 2 ,3) , w (M 2 ,4) ) ∈ Ω cd , (4.4b)
and

P cd (ω) = (n t ) t∈T P (n (M 1 ,1) )F (p (M 1 ,1) | n (M 1 ,1) ) × t∈T\(M 2 ,4) P (n t + | n t )F (p t + | n t + ) . (4.4c)
Additionally, we have already defined in Chapter 3, the finite set S ⊂ R |C| + of acceptable stock levels in the refinery. Therefore, we can affect an arbitrary probability to each element of S and build the underlying probability space (S, F st , P st ).

Finally, we denote by P M 3 ⊂ R |P| the finite set of values for products prices, where P is the set of existing products as presented in Chapter 3. We then affect a probabilty to each value to obtain the corresponding probability space (P, F pr , P pr ).

Subsequently, we set

Ω = Ω cd × S × P , (4.5a) F = F cd ⊗ F st ⊗ F pr , (4.5b)
the set of parts of Ω. We define the probability distribution

P(ω) = P cd (ω cd ) × P st (s) × P p (p) , ∀ω = (ω cd , s, p) ∈ Ω , (4.5c)
and obtain a probability space (Ω, F, P) that reflect the modeling of the sources of uncertainty we decided, jointly with TotalEnergies.

Multistage stochastic optimization problem

Now, we formulate a stochastic optimization problem. To that end, we consider the probability space (Ω, F, P) built in §4.3.1 that encompasses the sources of uncertainty {w t } t∈T , s and p. The anticipative criterion expressed in (4.2a) now becomes

E {w t } t∈T ,s M 3 ,p M 3 Ξ M 3 (s, {b t } t∈T , {w t } t∈T , p) . (4.6)
We then formulate the following stochastic optimization problem where random variables are identified in bold:

min {b t } t∈T E {w t } t∈T ,s,p Ξ M 3 s, {b t } t∈T , v, r, {w t } t∈T , p (4.7a) s.t t∈T b t ∈ D M 3 , (4.7b) b t ∈ B t , ∀t ∈ T , (4.7c) σ(b t ) ⊂ σ(w (M 1 ,1) , • • • , w t ) , ∀t ∈ T , (4.7d)
where we minimize the expected value of the economic function Ξ over purchases, consumption and settings controls.

The constraint (4.7b) forces the crude orders to respect certain requirements such as crude incompatibilities or categories.

The constraint (4.7d) is a nonanticipativity constraint. The σ-algebra generated by b t being included in the σ-algebra generated by (w (M 1 ,0) , • • • , w t ) expresses that the decision b t is made in reaction to w t , with full knowledge of the past, but not of the future.

We then develop Ξ M 3 to get a more convenient formulation of the Problem (4.7), namely min

{b t } t∈T E {w t } t∈T s M 3 ,p M 3 t∈T Ω t (b t , w t ) + Ψ M 3 s M 3 , t∈T b t , p M 3 (4.8a) s.t t∈T b t ∈ D M 3 , (4.8b) b t ∈ B t , ∀t ∈ T , (4.8c) σ(b t ) ⊂ σ(w (M 1 ,1) , • • • , w t ) , ∀t ∈ T . (4.8d)

Conclusion

In this Chapter 4, we used the variables introduced in Chapter 3 to build multistage stochastic optimization problems. Finally, in §4.3, we developed a stochastic model for the sources of uncertainty identified in Chapter 3 and ended up formulating a multistage stochastic optimization problem.

In Chapter 5, we will reformulate the Problem (4.8) into a stochastic optimal control problem after having introduced a state variable.

Chapter 5

Stochastic optimal control formulation 5.1 Introduction

In this Chapter 5, we reformulate the multistage stochastic optimization problem from Chapter 4, Problem (4.8), as a stochastic optimal control (SOC) problem.

First, in §5.2, we introduce a state variable, that we refer to as buffer, and obtain a first SOC problem. This problem is then refined when we introduce the notion of target constraint and viability set. Then, in §5.3, we define what we call a policy in the context of the SOC problem formulated in §5.2.

Optimal control formulation

The problem expressed in (4.8) is a multistage stochastic optimization problem. In §5.2.1, we introduce a family of state variables that we use to propose a stochastic optimal control formulation in §5.2.2. Then, in §5.2.3, we reformulate the coupling constraint on purchases as a constraint on the final state that we call a target constraint. We use the notion of viability sets to reformulate the target constraint as a series of constraint on the controls every week. Doing so enables us to reduce the size of both control sets and state sets.

Introduction of buffers

In Figure 4.1, and as detailed throughout §3.3.1.2 and §3.3.2.1, crude shipments are purchased every week but the delivery occurs only once, leading to an accumulation of pending orders until delivery. We introduce a new variable

d t = t ′ <t b t ′ ∈ R |C| , ∀t ∈ T ∪ {(M 3 , 1)} .
(5.1a)

This new variable d t represents a buffer made of the accumulation of all past purchases. Additionally, d (M 3 ,1) represents the variable after all purchases in T have been performed. While d t represents the sum of all shipments purchased before week t, d (M 3 ,1) also represents the agreagation of all shipments that are delivered to the refinery at the beginning of the month M 3 . Equivalently, (5.1a) can be written as a dynamic equation

d t + = d t + u sf t , ∀t ∈ T , (5.1b) d (M 1 ,1) = 0 .
(5.1c)

Stochastic optimal control formulation

For the sake of clarity we proceed to the following identification

t = min T = (M 1 , 1) , (5.2a) t = max T = (M 2 , 4) , (5.2b)
t + = (M 2 , 4) + = (M 3 , 1) . (5.2c)
With the buffer as defined in (5.1a), we have

d (M 3 ,1) = t∈T b t , (5.2d)
and we can reformulate (4.8) using the state candidate d introduced in §5.2.1

min {b t } t∈T {d t } t∈T∪{t + } E {w t } t∈T ,w M 3 t∈T Ω t (b t , w t ) + Ψ M 3 (s M 3 , d t + , p M 3 ) (5.3a) s.t d t + ∈ D M 3 , (5.3b)
d t ∈ R |C| + , ∀t ∈ T , (5.3c) d t = 0 , (5.3d)
d t + = d t + b t , ∀t ∈ T , (5.3e) b t ∈ B t , ∀t ∈ T , (5.3f) σ(b t ) ⊂ σ(w t , • • • , w t ) , ∀t ∈ T , (5.3g) σ(d t ) ⊂ σ(w t , • • • , w t ) , ∀t ∈ T .
(5.3h)

The constraint (5.3b) is a state constraint at the end of the finite timespan T, that is, a target constraint. The initialization of the state is ensured by (5.3d) and its evolution is handled by (5.3e).

Rewriting of the target constraint as state and control constraints

We presented the constraint (5.3b) as a target constraint on the final state d M 3 . In this §5.2.3, we reformulate this constraint as a series of state constraints.

We now recursively build a family {D t } t∈T of sets defined by

D t + = D M 3 , (5.4a) D t = {d t ∈ D , ∃b t ∈ B t | d t + b t ∈ D t + } , ∀t ∈ T .
(5.4b)

The set D t is built as the set of buffers from which it is possible, by an admissible control, to get to another element of D t + at the next stage. Following [START_REF] De | Sustainable management of natural resources: mathematical models and methods[END_REF], we call those sets, viability sets.

Additionally, we define a family { B t } t∈T set-valued mappings by

B t : D t -→ 2 B t (5.4c) d -→ {b ∈ B t | d + b ∈ D t + } .
The set B t (d) is built as the set of controls, at t, that ensure that the buffer d t + is viable too. The computation of both {D t } t∈T and { B t } t∈T can be performed offline. The motivating factor for performing this precomputation is that, by design, we reduce the number of possible controls with

| B t (d)| ≤ |B t | , (5.5)
thus resulting in a problem (5.6) of smaller size and without state constraints (except for the initialization in t = (M 1 , 1)). min

{b t } t∈T {d t } t∈T∪{t + } E {w t } t∈T ,w M 3 t∈T Ω t (b t , w t ) + Ψ M 3 (s M 3 , d t + , p M 3 ) (5.6a) s.t d t = 0 C , (5.6b)
d t + = d t + b t , ∀t ∈ T , (5.6c) b t ∈ B t (d t ) , ∀t ∈ T , (5.6d) σ(b t ) ⊂ σ(w t , • • • , w t ) , ∀t ∈ T , (5.6e) σ(d t ) ⊂ σ(w t , • • • , w t ) , ∀t ∈ T .
(5.6f)

Definition of a policy

The nonanticipativity constraint (5.6e) in Problem 5.6 indicates that the decision b t is taken in reaction to the revelation of the past (w (M 1 ,1) , . . . , w t ). Additionally, we were able to introduce a state d t in §5.2.1 accumulates all the crude oil purchased for M 3 up to the week t. Under the hypothesis of independent sources of uncertainty, this state condenses, at the beginning of week t, all the useful information to make a purchase decision in week t. d t and w t are the two inputs upon which the purchase depends on in the formula,

b t = ϕ t (d t , w t ) . (5.7)
We denote by Φ = {ϕ t } t∈T a family of functions

ϕ t : R |C| × R |P| -→ R |C| (5.8) (d, w) -→ ϕ t (d, w) ,
that forms a policy.

To assess the performance of a policy, we simulate it on a set of test scenarios, W test .

Conclusion

In this Chapter 5, we reformulated the multistage stochastic optimization problem from Chapter 4 as a stochastic optimal control problem. To that end, in §5.2, we have proposed a state, the buffer, that accumulates all the purchases yet to be delivered for the month M 3 , which evolution is guided by a dynamic equation. Additionally, by computing viability sets and control sets, we reduced the complexity of the problem resolution. Then, in §5.3, we briefly detailed what a policy is in the context of the SOC problem formulated beforehand.

The next Chapter 6 is devoted to the design of policies to tackle this SOC problem.

Chapter 6

Policy design

Introduction

In this Chapter 6, we present different methods to design policies dealing with the optimization problems formulated in Chapter 4 and Chapter 5.

First, in §6.2, we detail the construction of Ψ M 3 , an approximate production function of the refinery that we use in the policies instead of Ψ M 3 . Then, in §6.3, we focus on the design methods using a single scenario. This encompasses Expert, the method currently used by TotalEnergies as well as two other policies, Triplet and Model Predictive Control (MPC). In §6.4, we design methods using dynamic programming. We first detail the propagation of the target constraint introduced in §5.2. We then outline the standard application of Stochastic Dynamic Programming (SDP esp ) to produce a policy, using value functions computed offline. Then, we introduce a risk measure, the conditional value at risk, in the stochastic dynamic programming (SDP CVaR ). Finally, we propose a last policy that takes advantage of the time available before making each decision to recompute value functions. We call it successive-SDP (Suc-SDP).

Design of an approximate production function

The production function Ψ M 3 of the refinery for the month M 3 was introduced in §3.3.2, through Equation (3.16). Given stocks levels s, shipment deliveries d and, product prices p, Ψ M 3 returns the operational "cost" of the refinery during the month M 3 . This encompasses product sales as well as the charges incurred by running a refinery. In practice, there is no analytical expression for Ψ M 3 and its value is obtained numerically through the use of a software, that simulates the inner-working of the refinery. Unfortunately, such software is too costly, time-wise, to assess policies in a Monte-Carlo simulation. We therefore open up the function Ψ M 3 in order to build a new production function Ψ M 3 that we will be able to use in the policies that we will detail in §6.3 and §6.4. We recall from §3.3.1.2, the set C of crudes on the market is split in diverse families

C = l∈L C l , (6.1)
witch L the set of families we consider. After discussion with TotalEnergies, the refinery processes crudes in a certain order, depending on the category they belong to.

As an example, we consider three families and C = C 1 ∪C 2 ∪C 3 . The M 3 -buffer as introduced in §5.2.1 now splits into

d t = (d 1 t , d 2 t , d 3 t ) ∈ R |C| + , (6.2a)
with

d 1 t ∈ R |C 1 | + , (6.2b)
d 2 t ∈ R |C 2 | + , (6.2c)
d 3 t ∈ R |C 3 | + , (6.2d)
Now, let us assume that crudes must be processed in a specific order

C 1 -→ C 2 -→ C 3 . (6.3)
After discussion with TotalEnergies's engineers, in this situation, crudes are consumed sequentially, by couple. Opening the blackbox, Ψ M 3 can be expressed as the sum of three functions 1) , p M 3 (6.4) 1) ,

Ψ M 3 (s M 3 , d (M 3 ,1) , p M 3 ) = g M 3 s M 3 , 1 2 d 1 (M 3 ,
+ g M 3 1 2 d 1 (M 3 ,1) , 1 2 d 2 (M 3 ,1) , p M 3 + g M 3 1 2 d 2 (M 3 ,
1 2 d 3 (M 3 ,1) , p M 3 .
The function g M 3 is called the single period production function. Unlike Ψ M 3 , it takes as arguments crude oils that are processed at the same time. In TotalEnergies's setting, the value of g M 3 is numerically obtained using a software called Grtmps. In (6.4), we consider that the consumption of each buffer is evenly split between two sequences.

Further, the value of g M 3 (d 1 , d 2 , p) is the result of an optimization problem. The software Grtmps not only simulates the inner-working of a refinery in a "single period", it also optimizes the settings of the refinery so as to minimize the costs. We represent this optimization problem as

g M 3 (d 1 , d 2 , p) = min r M 3 ĝM 3 (d 1 , d 2 , r M 3 , p) , (6.5a)
s.t r M 3 ∈ R M 3 ,
where r M 3 are the settings of the refinery, and R M 3 , the set of possible settings. g M 3 is the cost function the Grtmps software minimizes. As a by-product of this optimization, the Grtmps software yields a mass balance λ M 3 (d 1 , d 2 , p) ∈ R |P| of products, with P the set of products as introduced in §3.3.2.2. In this approximation we ignore all cost except product sales so that

g M 3 (d 1 , d 2 , p) ≃ λ M 3 (d 1 , d 2 , p) × p . (6.6)
Although we have approximated g M 3 , computing λ M 3 is just as costly. After discussion with TotalEnergies, we obtained a reference product prices vector p ref and used it to compute a reference mass balance function

λ ref M 3 (d 1 , d 2 ) = λ M 3 (d 1 , d 2 , p ref M 3 ) . (6.7a)
We denote

g M 3 (d 1 , d 2 , p) = λ ref M 3 (d 1 , d 2 ) × p , (6.7b)
the resulting approximate version of g M 3 . We now buid the approximate production function Ψ M 3 as

Ψ M 3 (s M 3 , (d 1 (M 3 ,1) , d 2 (M 3 ,1) , d 3 (M 3 ,1) ), p M 3 ) = λ ref M 3 (s M 3 , d 1 (M 3 ,1) ) (6.7c) + λ ref M 3 (d 1 (M 3 ,1) , d 2 (M 3 ,1) ) + λ ref M 3 (d 2 (M 3 ,1) , d 3 (M 3 ,1) ) × p M 3 .
The approximate production function Ψ M 3 acts as if the refinery always runs in the same way, independently of the products prices. Therefore, while precomputing all the values of λ ref M 3 still requires calls to the Grtmps software, using Ψ M 3 does not involve such costly computations.

Single scenario based policies

In this section, we present three methods that rely on a single scenario to build a purchase policy. In §6.3.1, we detail the Expert method, the method currently used by TotalEnergies to purchase crude oil. In §6.3.2,we present the Triplet method, a policy that builds on Expert but proceeds to a single optimization rather than multiple successive optimizations. The, in §6.3.3, we develop the usual MPC policy, in which a future scenario is envisioned and the decision taken optimizes along that path.

At the beginning of each week t = (m, w), not only is the prime vector w t revealed, but a projection

p M 3 ∈ R |P| (6.8)
is given by the trading department to the decision maker. For the sake of clarity in algorithms, p M 3 is not indexed by the time t even though it is updated every week. The vector p M 3 is a vision, at the beginning of week t, of what the prices of products might be during the month M 3 . We do not discuss how p M 3 is obtained, but we explain how it is used to design a policy. Similarly, a projection of the stock s M 3 ∈ R |C| is provided to the decision maker at the beginning of each week t.

Current expert practice of optimization

To determine what crude oil to purchase each week, the method currently used by TotalEnergies relies on successive optimizations. As introduced in (3.5b), crudes are broken down into categories. Here there are three categories: balanced, heavy and light and the exact crudes can be found in (3.5). We recall that each crude is only available for purchase at single week, and in given volumes, as described in §3.3.1.2. In the case of three categories L = {1, 2, 3}, and a subdivision C = C 1 ∪ C 2 ∪ C 3 the crude purchases in week t are yielded by the Algorithm 1, that we describe now.

The policy described in Algorithm 1 consists in performing a series of static, deterministic, sequential optimizations every week.

At the beginning of week t, once the vector w t of premiums has been revealed, a projection p M 3 of product prices, as well as a stocks projection s M 3 , are communicated to the decision maker.

Then, the decision maker ranks every crude based on those two pieces of information using TotalEnergies's tool Grtmps represented by the function g M 3 introduced in §6.2, which optimizes the inner working of the refinery. In this policy, we use its approximation g M 3 instead. Then, the decision maker obtains, for each crude c a value corresponding to an operational margin if he were to buy crude c Algorithm 1 Expert purchase policy

procedure ϕ conv t (d t , w t ) A projection p M 3 of p M 3 is given A projection s M 3 of s M 3 is given if no crude belonging to the family 1 is in d t then (c 1 * * , g 1 * * ) = arg min c∈C 1 g c ∈G c t Ω t (g c , w t ) + g M 3 ( s M 3 , 1 2 g c , p M 3 ) if c 1 * * is available in t then purchase it in quantity g 1 * * end if end if if no crude belonging to the family 2 is in d then (c 2 * * , g 2 * * ) = arg min c∈C 2 g c ∈G c t Ω t (g c , w t ) + g M 3 (g 1 * * , g c , p M 3 )
▷ where g c 1 * * is either the crude purchased just before, the crude of family 1 in d t , or s M 3 if no such crude has been purchased yet if c 2 * * is available in t then purchase it in quantity g 2 * * end if end if if no crude belonging to the family 3 is in d then (c 3 * * , g 3 * * ) = arg min

c∈C 3 g c ∈G c t Ω t (g c , w t ) + g M 3 (g 2 * * , g c , p M 3 )
▷ where g c 2 * * is either the crude purchased just before, the crude of family 2 in d t , or s M 3 if no such crude has been purchased yet if c 3 * * is available in t then purchase it in quantity g 3 * * end if end if end procedure at price w t and sell the resulting products at price p M 3 . The crude selection is then performed sequentially for each crude family, the order in which categories are treated being set by the order in which crudes must be processed according to (6.3). For each crude family, as long as the total purchases do not infringe on the total purchase constraint

(M 2 ,4) t=(M 1 ,1) b t ∈ D M 3 expressed in §4.3, if the best
ranking crude (or one of the two best ranking as a variation) is available, then it is purchased; else, nothing happens and the decision maker waits for the next week. For the sake of clarity, in Algorithm 1, when writing g M 3 (g c 1 * * , g c , w, p M 3 ), g c is identified to (0, . . . , 0, g c , 0, . . . , 0) ∈ R |C| + , the vector of volumes with only its c-th component filled.

Triplets method

The Triplet policy is a variation of the Expert policy presented in §6.3.1. In week t, given a premium vector w t and a projection f products prices p M 3 , the decisionmaker now values crude combinations instead of individual crudes. Then, any of the crudes present in the best combination that is available in week t is purchased.

Algorithm 2 Triplet purchase policy procedure ϕ tri t (d t , w t ) A projection p M 3 of p M 3 is given A projection s M 3 of s M 3 is given Compute DM 3 (d t )
, the crude combinations that can still be reached from

d t c 1 * * ,g 1 * * c 2 * * ,g 2 * * c 3 * * ,g 3 * * = arg min (c 1 ,c 2 ,c 3 )∈ DM 3 (d t ) g c 1 ∈G c 1 t ,g c 2 ∈G c 2 t ,g c 3 ∈G c 3 t Ω t ((g c 1 t , g c 2 t , g c 3 t ), w t )+ Ψ M 3 ( s M 3 , (g c 1 t , g c 2 t , g c 3 t ), p M 3 )
Purchase any of the crudes c 1 * * , c 2 * * , c 3 * * that is available for purchase in week t end procedure

In Algorithm 2, every week, the decision maker computes the set DM 3 (d t ) ⊂ D M 3 that corresponds to all the crude combinations (triplets) that can still be reached given the state of the buffer d M 3 . Those combinations are then ranked based on their projected valuation, using w t and the projections p M 3 and s M 3 .

Any crude, from the best combination, that happens to be available for purchase in week t is purchased (the resulting command can correspond to not buying crude at t). In Algorithm 2 as well as in Algorithm 1, the only future scenario that is considered is the couple ( s M 3 , p M 3 ) of projections that is given to the decision maker at the beginning of each week.

Model predictive control policy (MPC)

Model Predictive Control (MPC) is a policy frequently used in the control of dynamic systems. In Algorithm 4, instead of performing a static optimization like in §6. 3

{b * t ′ } t ′ ⪰t = arg min {b t ′ } t ′ ⪰t t t ′ =t Ω t ′ (b t ′ , w t ′ ) + Ψ M 3 ( s M 3 , d t + , p M 3 ) , s.t d t + ∈ D t + , d t ′+ = d t ′ + b t ′ , ∀t ′ ∈ t, t , b t ′ ∈ B t ′ (d t ′ ) , ∀t ′ ∈ t, t . Return b * t end procedure
In Algorithm 4, the decision-maker uses a single scenario to make the purchase decision b t . Unlike in §6.3.2, the scenario includes crude premiums in addition to the stock and product prices predictions. While the values used for the stock s M 3 and the product prices p M 3 are the predictions given to the decision maker, the crude premiums are the mean scenario of multiple projected scenarios that fit the stochastic model presented in §4.3.1. The method used to build such scenarios is similar to the algorithm that will be presented in §7.2.

(w t , w t + , . . . , w (M 2 ,4) , s M 3 , p M 3 ) ∈ R (t-t+1)×|C| × R |C| + × R |P| . (6.11)
Whereas the products prices and stocks projections are given respectively by the trading department and the production department, the decision-maker needs to buid the premiums projection himself using Algorithm 12. Once the projected scenario complete, the decision-maker solves a deterministic optimization problem that spans the remaining duration [t, t] and is parametrized by the buffer

d t {b * t ′ } t ′ ⪰t = arg min {b t ′ } t ′ ⪰t t t ′ =t Ω t ′ (b t ′ , w t ′ ) + Ψ M 3 ( s M 3 , d t + , p M 3 ) , (6.12a) s.t d t + ∈ D t + , (6.12b)
d t ′+ = d t ′ + b t ′ , ∀t ′ ∈ t, t , (6.12c)
b t ′ ∈ B t ′ (d t ′ ) , ∀t ′ ∈ t, t . (6.12d)
The problem (6.12) is based on (5.3) formulated in §5.2.2. Solving it equates to planning all future purchases {b * t } t ′ ∈ t,t under the assumption that the scenario (w t , w t + , . . . , w t , s M 3 , p M 3 ) will happen. Once the solution obtained, the decision maker takes the decision b * t that concerns the week t.

Dynamic programming based policies

In §6.4, we detail three methods based on Stochastic Dynamic Programming (SDP). While the resolution methods from §6.3 only used a single projection, these methods use multiple projections to build policies. First, in §6.4.1, we detail the procedure followed to compute the viable decision sets introduced in §5.2.3. Then, in §6.4.2, we detail the computation of value functions using stochastic dynamic programming and their incorporation into policies (SDP esp and SDP CVaR ). Finally, in §6.4.3 we present a policy called "successive SDP" (Suc-SDP) in which the value functions are recomputed at every stage. Designing each of these policies requires a great number of scenarios that fit the stochastic model detailed in §4.3.1. Such a set of scenarios is called design set. For now, we do not detail the method used to create such a set, this will be done in §7.2 were we detail the algorithms used.

Target constraint propagation algorithm

We detail the algorithms allowing us to obtain both the family {D t } t∈T∪{t + } of viability state sets and the family { B t } t∈T of viable control mappings, respectively introduced in (5.4b) and (5.5). We propose the Algorithm 5 to recursively compute the family {D t } t∈T , of viable state sets given by the induction (5.4b). The execution of Algorithm 5 is only possible because the decision sets B t are finite, thus making the enumeration of the decisions and states possible.

Algorithm 5 Backward computation of the viability state set D t procedure D t -(D t , B t -) D t -= {∅} ▷ start with an empty set for d ∈ D t do for b ∈ B t -do d ′ = (d -b) + D t -← D t -∪ {d ′ }
▷ progressively add the right elements end for end for end procedure

The algorithm is initialized with the set

D t + = D M 3 , introduced in §3.3.2.

Stochastic dynamic programming (SDP)

As seen in §5.2, the buffer variable d t serves as a state variable. We adapt the multistage stochastic optimization problem (5.6) to the approximate production function Ψ M 3 built in §6.2.

min {b t } t∈T {d t } t∈T∪{t + } E {w t } t∈T ,w M 3 t∈T Ω t (b t , w t ) + Ψ M 3 (s M 3 , d t + , p M 3 ) (6.13a) s.t d t = 0 C (6.13b) d t + = d t + b t , ∀t ∈ T (6.13c) b t ∈ B t (d t ) , ∀t ∈ T (6.13d) σ(b t ) ⊂ σ(w t , • • • , w t ) , ∀t ∈ T (6.13e) σ(d t ) ⊂ σ(w t , • • • , w t ) , ∀t ∈ T . (6.13f)
Since (6.13) is formulated as an optimal control problem, we can build a policy using Stochastic Dynamic Programming.

Dynamic programming equation

We write the dynamic programming equations associated with (6.13) as

V t + (d) = E s M 3 ,p M 3 Ψ M 3 (s M 3 , d, p M 3 ) , ∀d ∈ D t + , (6.14a) V t (d) = E w t min b∈ B t (d) Ω t (b, w t ) + V t + (d + b) , ∀d ∈ D t , ∀t ∈ T . (6.14b)
The value functions {V t } t∈T∪{t + } are computed recursively in Algorithm 7.

Algorithm 7 Recursive computation of the value functions The value function V t + defined in (6.14b) serves as a final cost. V t + (d) is the average value of the production function for the buffer d. The decision maker runs Algorithm 7 before the start of the month M 1 as all the value functions {V t } t∈T must have been computed before taking any decision.

procedure Computation of {V t } t∈T∪{t + } for d ∈ D do for p M 3 ∈ p i M 3 i∈ 0,9 do for s M 3 ∈ {s 1 M 3 , s 2 M 3 , s 3 M 3 , s 4 M 3 } do Compute Ψ M 3 (s M 3 , d, p M 3 ) end for end for V t + (d) = E s M 3 ,p M 3 Ψ M 3 (s M 3 , d, p M 3 ) end for t =

Dynamic programming with a risk measure

In §6.4.2, we computed value functions using an expectation. Here, we compute value functions using a different risk measure. The expected value E is risk neutral, as it gives equal importance to good results (e.g small loss / high gains) and poor ones (e.g important loss/ negative gains). In practice, the decision maker is rarely risk-neutral and will give more importance to avoiding bad outcomes rather than improving solely the average result. One risk measure used to that end is the Conditional Value at Risk (CVaR).

We recall the definition of the CVaR for a discrete loss variable X and a risk level

β ∈ [0, 1] CVaR β (X) = E[X | X ≥ V aR β (X)] , (6.15a)
where V aR(X) is the value at risk, defined as

V aR β (X) = min{z|P (X ≤ z) ≥ β} . (6.15b)
Letting λ ∈ [0, 1], we combine the CV aR with the expected value in the risk measure

ρ β λ (X) = (1 -λ)E(X) + λ CVaR β (X) , (6.16)
taht is, the risk measure giving the weight λ to the CVaR conditioned to β percents. This is the risk measure we use to write new dynamic programming equations:

V λ,β t + (d) = ρ β λ Ψ M 3 (s M 3 , d, p M 3 ) , ∀d ∈ D t + , (6.17a)
V λ,β t (d) = ρ β λ min b∈ B t (d) Ω t (b, w t ) + V λ,β t + (d + b) , ∀d ∈ D t , ∀t ∈ T . (6.17b)
The Algorithm 8 details the computation of the value functions {V λ,β t } t∈T and follows Algorithm 7 in its structure. The complexity of Algorithm 8 is the same as Algorithm 7, with the exception of the computation of the CVaR.

Step forward optimization

Once value functions {V t } t∈T have been computed, either using the expected value or a risk measure, we can express the policy as Algorithm 9:

While the computation of value functions {V t } t∈T is expensive, as detailed in §6.4.2.1, the execution of the policy through Algorithm 9 is light as the decision maker only needs to enumerate a finite number (| B t (d)|) of viable decisions in week t and chose the one yielding the best result. In the application presented in Chapter 7, an average of 8 viable decisions are tested each week, compared to an average of 40 possible decisions, that is a 5× gain. The computation gains provided by the propagation of the target constraint detailed in §6.4.1 are also visible in the online phase of the SDP-based policy.

Algorithm 8 Recursive computation of the value functions with a CVaR

procedure Computation of {V λ,β t } t∈T∪{t + } for d ∈ D do for p M 3 ∈ p i M 3 i∈ 0,9 do for s M 3 ∈ {s 1 M 3 , s 2 M 3 , s 3 M 3 , s 4 M 3 } do Compute Ψ M 3 (s M 3 , d, p M 3 ) end for end for V t + (d) = ρ β λ Ψ M 3 (s M 3 ,
Ω t (b, w t ) + V t + (d t + b) , (6.18)
Return b * t end procedure

Successive SDP

One particular aspect of the crude oil procurement is the time available between the revelation of premium prices w t at the beginning of a week and the moment the order b t must be placed. The typical time available to make a decision is 48 hours, up to 72 hours.

The implementation of SDP as presented in §6.4.2 requires a lot of offline computation but leads to a light policy; once value functions have been computed offline, taking a decision is rather simple as shown in §6. [START_REF] Bellman | Dynamic Programming[END_REF]

Recompute V t + (d) = E s M 3 ,p M 3 Ψ M 3 (s M 3 , d, p M 3 ) , ∀d ∈ D M 3 t ′ = t while t ′ ≻ t do for d ∈ D t ′ do Recompute V t ′ (d) = E w t ′ min b t ′ ∈ B t ′ (d) Ω t ′ (b t ′ , w t ′ )+V t ′+ (d +b t ′ ) , end for t = t - end while Return b * t = arg min b∈ B t (d t ) Ω t (b, w t ) + V t + (d t + b) end procedure
Here, the projections given to the decision maker every week serve as a basis for the creation of many scenarios. Those scenarios are then used to recompute new value functions {V t ′ } t ′ ≻t by stochastic dynamic programming. The decision-maker then takes the decision b minimizing Ω t (b, w t ) + V t + (d t + b). The next week, a new price projection p and a new stock projection s are communicated, new scenarios are generated and new value functions are computed.

Conclusion

In Chapter 6, we have presented six purchase policies to solve the problem formulated in Chapter 4 and Chapter 5. The designed policies are divided into two categories. On the one hand, the methods detailed in §6.3.1, §6.3.2 and §6.3.3 only use a single scenario that is a projection, to make a decision. On the other hand, the methods introduced in §6.4.2.1, §6.4.2.2 and §6.4.3 use multiple scenarios to build value functions that are then used in their respective policies to make a decision. Stochastic Dynamic Programming can be used either with the expected value, or with another risk measure. In §6.4.3, we leverage the time available every week to make a purchase decision, and we use the price projections communicated every week to generate new scenarios and recompute value functions.

Next, in Chapter 7, we will detail a numerical application on which we test each policy designed in Chapter 6 and discuss the results.

Chapter 7

Numerical results

Introduction

In this Chapter 7, we present numerical assessments of the policies presented in Chapter 6.

First, in §7.2, we detail the algorithms used to build an assessment set of scenarios. In §7.3, we use the set built in §7.2 to assess six policies and compare them on the basis of their payoff distribution. Last, in §7.4, we assess the same policies on six historical scenarios that play back past months of 2020 and 2021.

Before all, we present the structure of the procurement problem we deal with in this Chapter 7. We recall that, during two months M 1 and M 2 , there are eight weeks during which three crudes have to be bought. In Figure 7.1, we display the availability timeline of the crudes throughout the months of years M 1 and M 2 .

We recall that crudes are categorized according to their characteristics. We consider 3 families: balanced, heavy, light. No more than one shipment of heavy and one shipment of light crude oil can be purchased.

After discussion with TotalEnergies's engineers, it was deemed necessary to distinguish the order in which the combination of crudes arriving at the beginning of the month M 3 would be processed. As an example, processing (B5 → H6 → L3) would not yield the same result as processing (L3 → H6 → B5). As a consequence, we must distinguish, for each crude, whether it is purchased to be consumed in first, second, or third position. The number of crudes considered is tripled: instead of having just B5, we denote B5 1 (resp B5 2 and B5 3 ) the crude B5 that is available for a consumption in the first position (resp. second, third). This modeling trick makes it possible to retain the problem used in Chapter 4 while respecting the additional order constraint imposed by TotalEnergies. While we consider only 19 crudes, the formal number of crude we deal with is triple. Using the notations from Chapter 3, this implies that |C| = 3 × 19 = 57. We now formally have 9

1 M1 2 3 4 1 M2 2 3 4 1 M3 w (M1,1) w (M1,2) w (M1,3) w (M1,4) w (M2,1) w (M2,2) w (M2,3) w (M2,4) sM 3 , pM 3 B1 1 B2 1 B3 1 B4 1 B5 1 H1 1 H2 1 H3 1 H4 1 H5 1 H6 1 L1 1 L2 1 L3 1 L4 1 L5 1 L6 1 L7 1 L8 1 B1 2 B2 2 B3 2 B4 2 B5 2 H1 2 H2 2 H3 2 H4 2 H5 2 H6 2 L1 2 L2 2 L3 2 L4 2 L5 2 L6 2 L7 2 L8 2 B1 3 B2 3 B3 3 B4 3 B5 3 H1 3 H2 3 H3 3 H4 3 H5 3 H6 3 L1 3 L2 3 L3 3 L4 3 L5 3 L6 3 L7 3 L8 3

Assessment set construction

In §7.2, we detail the procedures used to generate the assessment set of scenarios that will be used in §7.3 to perform the Monte-Carlo simulation. As introduced in §5.3, we recall that a scenario is a sequence

w (M 1 ,1) , w (M 1 ,2) , w (M 1 ,3) , w (M 1 ,4) , w (M 2 ,1) , w (M 2 ,2) , w (M 2 ,3) , w (M 2 ,4) , s M 3 , p M 3 , (7.1)
where [START_REF] Bellman | Dynamic Programming[END_REF] is the series of crude premiums over the two months M 1 and M 2 , s M 3 is the stock inside the refinery at the beginning of the month M 3 , p M 3 is the price of the finished products for the month M 3 .

w (M 1 ,1) , w (M 1 ,2) , w (M 1 ,3) , w (M 1 ,4) , w (M 2 ,1) , w (M 2 ,2) , w (M 2 ,3) , w (M 2 ,
For each scenario, the three parts will be built independently of each other, according to the stochastic model built in §4.3.1. In §7.2.1 we present the Markovian model used to draw series of crude premiums. Then, in §7.2.2 and §7.2.3 we present the data used as possible stock and product price values.

Crudes premiums

In §4.3.1 we presented the stochastic model for crude premiums. Using a hidden Markov chain model, we consider that crude premiums are not independant from one week to the other. In §7.2.1.1, we present the data available to us for the numerical application and its pre-processing. Then, in §7.2.1.2, we present the algorithms used to build the hidden Markov chain model and draw premiums scenarios.

As presented in the introduction, there are 3 physical crude families:

Premiums data pre-processing

In practice, the history of weekly crude premiums is not readily available. We are now going to detail, how we used the raw data provided by TotalEnergies to produce an history of weekly premiums as well as an estimate of the distribution of crude oil premiums for each crude. Figure 7.2 illustrates the raw data available where each crude is represented by a 4 letters code. BBF O marks the reference crude quotation. For every other crude, the column "Fob" corresponds to the premium of the crude plus the reference quotation discussed in §3.2.1. Using the historical data available (which Figure 7.2 is an extract of), we build an history of the premiums for each crude in C, over the last 10 years. For instance, on the date 05/03/2020, the premium of the crude coded BBGA is 111, 215-110, 495 = 0, 712$/bbl. In doing so, we obtain, for each crude, the daily history of the premiums over the last 10 years. These daily values are then converted into weekly values by averaging the premiums over each week. As an example, to obtain a premium value for crude c in the week 18 of 2013, we do In Figure 7.3, we display the histogram of reference quotations over the last 10 years. In this numerical application, motivated by the hedging performed by TotalEnergies, we made the choice to dismiss the reference quotation as a source of uncertainty. In the assessment scenario, the reference has a fixed value. However, we observe that the distribution resembles a mixture of Gaussian-like distributions. Now, in Figure 7.4, we display the histogram of daily premiums for the crude B5 over the last 10 years. We note that this distribution resembles a Gamma distribution. So as to estimate the parameters, we obtain the shape and scale of each distribution using a maximum-likelihood method. We thus associate to each crude c a Gamma density with parameters (κ c , θ c ) given by (7.3)

f (w, κ c , θ c ) = w κ c -1 e -w θ c Γ(κ c )θ c κ c . (7.3)
In particular, we estimated the parameters κ B5 = 3.19, θ B5 = 0.48 (shape, scale) for the crude B5. This distribution is displayed in Figure 7.4. We have an history of weekly averaged crude premiums and estimation of the premium distribution for each crude. We now use both of these elements to build transition matrices for the hidden Markov chain model of premiums.

Hidden Markov chain construction

As detailed in §4.3.1, the hidden state of the Markov chain that we model can be divided in three parts, one for each category. We denote by

n t = (n b t , n h t , n l t ) , (7.4a
)

n l t ∈ {1, 2, 3, 4} , ∀l ∈ {b, h, l} , (7.4b)
the hidden state for week t. The term n l t codes the state of the market for the family l: 1 corresponds to the lowest price trend, and 4 to the highest price trend.

For a family l ∈ L in week t, n l t moves to the value n l t + in the next week t + (where t + is the successor to t as defined in §3.3.1.1) according to a transition matrix M l denoted

M l =     M l 1,1 M l 1,3 M l 1,2 M l 1,4 M l 2,1 M l 2,3 M l 2,2 M l 2,4 M l 3,1 M l 3,3 M l 3,2 M l 3,4 M l 4,1 M l 4,3 M l 4,2 M l 4,4     . (7.5)
As an example, let l be a crude oil category, and let t be a week. Let n l t = 2. Then, the random variable n l t + follows distribution defined by the second line of M l . More precisely, we have P (n l t + = i|n l t = 2) = M l 2,i . We now present the method used to compute each transition matrix M b , M h and M l Once the parameters for the Gamma distribution of each crude have been estimated in §7.2.1.1, we build the four following intervals for each crude c. Each interval is associated to a value of the corresponding hidden state n l t :

1

: [c, q 15% c [, (7.6a) 2 : [q 15% c , (κ c -1)θ c [, (7.6b) 3 :
[(κ c -1)θ c , q 75% c [, (7.6c) 4 :
[q 75% c , c] , (7.6d)
where c and c are the historic minimum and maximum of the premium for the crude c over the history. The quantities q 15% c and q 75% c are the quantiles at levels 15% and 75% for the estimated Gamma distribution . The term (κ c -1)θ c is the mode of the Gamma distribution with shape κ c and scale θ c .

We use Algorithm 11 to compute each of the 3 transition matrices used in the Markovian model: the 3 transition matrices correspond to heavy, balanced and light crudes. Given a crude family l, for each crude c ∈ C l , the algorithm scans the history of weekly-averaged crude premiums built in §7.2.1.1. Then, each weekly price is translated into an integer depending on its value relative to the intervals Algorithm 11 Construction of a transition matrix associated with the crude family l.

procedure Building M l ( (premium c w ) c∈C,w∈history ) Initialize M l as a 4 × 4 null matrix

for c ∈ C l do Create 4 intervals 1 : [c, q 15% c [, 2 : [q 15% c , (κ c -1)θ c [, 3 : [(κ c -1)θ c , q 75% c [, 4 : [q 75% c
, c] presented in (7.6) for each couple (w, w + 1) of weeks in history do compute i, the interval in which premium c w is compute j, the interval in which premium c w+1 is M l i,j ← M l i,j + 1 end for end for for i ∈ {1, 2, 3, 4} do for j ∈ {1, 2, 3, 4} do

M l i,j ← M l i,j / 4 j ′ =1 M l i,j ′
end for end for Return M l end procedure in (7.6). Week to week variations are then reported into the same matrix for each category. After renormalization, we obtain a transition matrix M l for each l ∈ L.

Once the transition matrices are computed for each family of crude l ∈ L, we use Algorithm 12 to draw scenarios of crude premiums trajectories (w t ) t∈T .

In Algorithm 12, we compute an initial state n t = (n l t ) l∈L from an initial vector w t of premiums. Then, we draw a tuple of states (n t ′ ) t ′ ≻t = (n l t ′ ) l∈L t ′ ≻t using the transition matrices {M l } l∈L computed using Algorithm 11.

Every week t ′ ≻ t, for every crude c, an exact prime value w c t is observed according to the estimated Gamma distribution from §7.2.1, restricted to the interval of (7.6) that corresponds to the hidden state. Looking back at §4.3.1, the observation law F C for crude c writes

F c (n) =          F ′ (κ c , θ c , c, q 15% c ) if n = 1, F ′ (κ c , θ c , q 15% c , (κ c -1)θ c ) if n = 2, F ′ (κ c , θ c , (κ c -1)θ c , q 75% c ) if n = 3, F ′ (κ c , θ c , q 75% c , c) if n = 4 . (7.7)
In (7.7), F ′ is a truncated Gamma distribution which expression is

F ′ (κ, θ, a, b) : [a, b] -→ [0, 1] (7.8)
w -→ f (w, κ, θ) φ(b, κ, θ) -φ(a, κ, θ)
where f is the Gamma distribution whose expression is in (7.3) and φ is the associated cumulative distribution function. Although f was built with daily premiums, it is still compatible with weekly values as these are averaged weekly values.

Stocks

In the monthly procurement problem, we are interested in buying oil during the first two months M 1 and M 2 for the refinery to run during the last month M 3 . The stocks vector s M 3 at the beginning of M 3 is the result of a dynamic relation using the deliveries and consumption over M 1 and M 2 . Instead, we treat it as a source of uncertainty. The reason for that decision is that, taking into account this dynamic requires to manage the production for several months, which is outside the scope of this problem.

As presented §4.3.1, this uncertainty is considered as independent of both the crude premiums and the product prices. We consider that s M 3 can take 4 different values. Each stock value corresponds to a popular crude in stock inside the refinery:

Algorithm 12 Generation of a scenario of premiums vectors each week t ′ ≻ t procedure Draw primes scenario(w t ) for l ∈ L do for c ∈ C l do n l,c t ←the interval number in which

w c t is 1 : [α c , µ c -σ c [, 2 : [µ c -σ c , µ c [, 3 : [µ c , µ c + σ c [, 4 : [µ c + σ c , ω c ] end for n l t ←-int 1 |C l | c∈C l n l,c
t ▷ mean value rounded to the nearest integer

end for t ′ = t while t + ⪯ t ′ ⪯ (M 2 , 4) do for each l ∈ L do n l t ′ ∼ M l (n l t ′-) ▷ n l t ′ follows a distribution parameterized by n l t ′- for c ∈ C l do w c t ′ ∼ F c (n l t ′ ) ▷ w c t ′ follows a distribution parameterized by n l t ′ end for w l t ′ = {w c t ′ } c∈C l end for w t ′ = {w l t ′ } l∈L t ′ → t ′ + end while Return scenario = (w t , w t + , . . . , w (M 2 ,3) ) end procedure

Products prices

While the series of crude premiums are drawn using a hidden Markov chain model, the product prices vectors are randomly selected from a pool of historical values. In Figure 7.5, we give an example of the data available for the product prices. Each column corresponds to a week and each line to a product. Each cell represents a price per quantity unit (either m 3 or tons). Here, the column corresponds to the prices during the week 31 of 2020 (07/27/2020 --08/02/2020) while the column 17 corresponds to the week 17 of 2021 (04/26/2021 -05/02/2021).

In the construction of the assessment scenarios, we randomly draw a number that corresponds to the week between the week 31 of 2020 and week 17 of 2021. The corresponding vector of product prices is then associated with the scenario being built. As a result, the product prices are drawn completely independently of both crude premiums and stocks.

Monte-Carlo simulation of policies

In this section we test each policy from Chapter 6 on the set of assessment scenarios built in §7.2. We present and analyze the results in the form of histograms. We first display the results of the Monte-Carlo assessment for each policy in §7.3.1.

Although each histogram gives a sense of the general behavior of each policy, comparing two policies along the same scenario is difficult. For that reason, in §7.3.2, we present histograms of the algebraic difference between two policies. Finally, in §7.3.3, we nuance the numerical results presented above.

We recall the six policies presented in Chapter 6, the first three policies only use a single scenario to make a decision while the other three use multiple scenarios:

Expert's opinion: In this policy, detailed in §6.3.1, the decision maker tests and ranks all crudes individually, family by family. If the best crude is available, it is purchased. The process is akin to static deterministic sequential optimization Triplet method: In this policy, detailed in §6.3.2, the decision maker tests and ranks all crude combinations that are still possible. Then, he purchases any crude from the best combination, that is available this week. This policy is also static deterministic optimization.

MPC method: In this policy, detailed in §6.3.3, the decision maker uses the prices of week t to build a projection of the future prices. He then proceeds to solving a dynamic deterministic problem over the remaining timespan t, t and takes the first optimal decision. SDP esp policy: In this policy, detailed in §6.4.2 we use the value functions computed in Equation (6.14) to solve a deterministic optimization problem in §6.4.2.3 which solution is the purchase decision.

SDP CVaR policy: In this policy, we solve the same problem in §6.4.2.3 but using different value functions. These are computed using a risk measure as detailed in §6.4.2.2.

Suc-SDP : In this policy, detailed in §6.4.3, new value functions are recomputed every week using the current products price projection and the currents crudes premiums. The decision maker then solves a static optimization problem to get the purchase decision.

The policies SDP esp , SDP CVaR and Suc-SDP are said to utilize multiple scenario because the value functions that are used make a decision have been computed using multiple scenarios.

Comparing policies by means of their respective histograms

Figure 7.6 represents the histograms of operating margins over the set W 1000 of 1000 assessment scenarios built using the tools from §7.2. The first observation is that both SDP -based policies seem to behave significantly better than the singlescenario based policies. As summed up in Table 7.1, on average SDP esp performs 70% better than the Expert policy, and 52% better than MPC.

Comparing policies scenario by scenario

The histograms presented in §7.3.1 give a good sense of how each policy performs individually. But comparing two policies can be tricky since we have no information whether or not the same scenarios give comparable results. To provide further information, we decided to compare policies, scenario by scenario. In Figure 7.7, we display the algebraic difference between SDP esp and Expert for the 1000 scenarios of the assessment set, and we plot the corresponding histogram. It appears clearly that, for many scenarios, the difference between the results of each policy is slim. In fact, the highest spike covers the interval [0, 1.10 6 [ and contains 461 scenarios while the second highest, corresponding to the interval [-1.10 6 , 0[ contains 150 scenarios. Additionally, as summed up in Table 7.3, there is a noticeable number of scenarios between the 5.10 7 and 1.5.10 8 marks that correspond to scenarios for which Expert leads to poor results, while SDP esp produces an acceptable solution.

It appears in Figure 7.8 that the distribution of differences is skewed in favor of SDP esp (towards the right, SDP esp > Expert). Expert and SDP esp produced the same margin in only 3 scenarios out of 1000. In those 3 scenarios, the decisions taken were the same. In Figure 7.9 we compare SDP esp and SDP CVaR and we observe that, in nearly 70% of scenarios the difference is less than 5.10 5 $. Upon closer inspection, in 635 scenarios out of the 1000 in the assessment set, SDP esp and SDP CVaR produce the same decisions.

Finally, we compare SDP esp to MPC in Figure 7.10. Although Table 7.1 indicates a smaller performance gap between SDP esp and MPC than between SDP esp and Expert, we notice than the histogram looks like that in Figure 7.7. MPC fared better than SDP CVaR in 352/1000 scenarios and both policies lead to the same purchases in a single case.

Shortcomings of Monte-Carlo assessment

In this section, we nuance the results presented in in §7.3.1 and §7.3.2.

First, the approximation Ψ M 3 of the production function Ψ M 3 made in §6.2 is of poor quality. This approximation was born out of necessity to overcome a computational hurdle but is not a faithful representation of how a refinery works. As explained in §6.2, Ψ M 3 was obtained using a reference vector p ref erence of product prices. As soon as product prices p M 3 differ "too much" from the reference, the approximation is no longer valid since TotalEnergies's tool, Grtmps, would operate of the refinery differently, yielding a different mass balance.

Second, the results from Expert need to be put back into context. TotalEnergies's actual method to purchase crude oil heavily relies on human knowledge, something that is difficult to translate into code. Therefore, Expert is a very dry version of TotalEnergies's actual process. According to Table 7.2, the decisions taken by Expert yield losses in more than 25% of the scenarios. This result does Third, even if they are treated as helping tools for the decision maker, the policies SDP esp and SDP CVaR show promising results. In the same test environment as the three other policies, they displayed a reduction of the bad cases (left tail of the histograms in Figure 7.6), leading to significant average gains. Additionally, we did not observe any significant behavior difference when changing the average in SDP esp for a risk measure in SDP CVaR , even with multiple different risk sensibilities.

Historical scenarios

In this section §7.4, we test each policy on a limited number of historical scenarios. We then discuss the sequences of decisions taken by each policy. Contrary to §7.3, the scenarios in §7.4 replay certain past months instead of inventing realistic values using the stochastic model developed in §4.3.1.

Historical scenarios construction

The numerical application in this Chapter 7 is centered around the month of December (M 3 = December) and it is the first month that we replay. Consequently, the approximation Ψ M 3 introduced in (6.7c), was obtained using a reference product prices vector p ref erence typical of the month December, given by TotalEnergies. For the refinery to operate in December we need to purchase oil in the months of October (M 1 = Ocotber) and November (M 2 = November) 2020. For ease of use, we denote the scenario of December 2020 by: w (O,1) , w (O,2) , w (O,3) , w (O,4) , w (N,1) , w (N,2) , w (N,3) , w (N,4) , s D , p D . This scenario, although labeled as historic, does not exist as is inside the data of TotalEnergies. Here, we detail what data is used, and how, to obtain the historical scenario from TotalEnergies's data:

Each crude premium vector w t is obtained by averaging the daily historical premiums of the crudes during the corresponding week, similarly to (7.2). The first week, (O, 1), spans 10/05 -10/09 and, the last week (N, 4) spans 11/23 -11/27. In The stock s D represents the crude oil in stock inside the refinery at the beginning of December. We consider this stock to be ≃ 120, 000 m 3 of B5 crude, that is,

s D = (0, • • • , 0, 120.000 position of B5 , 0, • • • , 0) . (7.10)
The vector of product prices p D is computed as the average of the product prices over the last four weeks of 2020 (49, 50, 51, 52). As an example on a product in Figure 7.12 In this section, we replay the month of December 2020 through the scenario built in §7.4.1 with each of the six policies from Chapter 6: Expert, Triplet, MPC, SDP esp , SDP CVaR and Suc-SDP. In Table 7.4, we display both the operational margin generated by each policy and the list of crudes purchased over the 8 weeks of October and November. Unsurprisingly in light of the Monte-Carlo results, Expert is the worst performing policy of the batch over the month of December. While SDP esp and SDP CVaR outperform both Expert and Triplet, they are bested by MPC. This result suggests that the product prices prediction p t provided by the trading each week is a valuable piece of information. By design, neither SDP esp nor SDP CVaR use this prediction, as incorporating it inside the state would make the size of the state explode. Accordingly, we observe that Suc-SDP manages to edge out MPC and actually achieves the optimum on the month of December. While significantly heavier than other policies as it requires recomputation of the value functions every week, this policy seems to marry the dynamic advantage of SDP esp with the prediction advantage of MPC.

Results for the months from November 2020 to March 2021

Having replayed the month of December 2021, which is the month around which the numerical application, and around which the approximation Ψ M 3 of the production function Ψ M 3 was tailored, we now test other historical scenarios. We test the historical scenarios of October and November 2020 as well as January, February and March 2021. Expert clearly appears as the worst performing policy overall. On the opposite, Suc-SDP is the best performing policy in 5 out of 6 scenarios, just in front of MPC. Most surprisingly, both SDP esp and SDP CVaR policies seem to struggle. Far behind MPC, they fail to produce a positive result for the months of January and February 2021. We note that for every month, except March 2021, Suc-SDP achieves the optimum. For March, the order is reversed and MPC is the best policy, even though it does not reach the optimum for that month. Looking back at Figure 7.1, both MPC and Suc-SDP take the same decisions up until week (M 2 , 2). At this point, Suc-SDP only purchases B5 while MPC purchases B5, B3 and H6.

Conclusion

In this chapter, we compared the policies presented in Chapter 6 in two complimentary ways. After detailing the construction of an assessment set of scenarios in §7.2, we tested, and compared, five policies in §7.3. While the scenarios from the assessment set are fictitious, the policies are tested on historical scenarios in §7.4 that replay each month from November 2020 to March 2021. The findings differed a lot from one type of assessment to the other.

While Suc-SDP could not be tested on a Monte-Carlo simulation due to computation limitations, SDP esp and SDP CVaR were clearly the best performing poli-cies, beating MPC by over 50% and Expert by over 70% on average. The results obtained on the historical scenarios come in stark contrast as both SDP esp and SDP CVaR performed below MPC and even Triplet, a policy close to Expert. While SDP esp and SDP CVaR performed better than Expert, the biggest surprise came from how close to the optimal MPC gets, and how it consistently beats SDP esp . On the historical scenarios, the only policy that fared better than MPC was Suc-SDP, which is much more demanding.

While these results highlight the potential of developing policies that take into account uncertainties into the procurement of crude oil, they also beg several questions. One key takeaway is that there is currently no good production function, or tool, to use in a multistage stochastic optimization setting. It also appears from the result discrepancies between the Monte-Carlo simulation and the historical scenarios that a better assessment set could, and should, be used. In particular, we should work on linking products prices to the crude oil premiums and change the way uncertainties are modeled in §4.3.1 and §7.2.

In the coming Part II, we will procure crude oil, not for one month like in Part I, but for any number of consecutive months. In that regard, we will expand upon the modeling and the formulation of Part I and add month-to-month stock dynamics.

93

Part II

General procurement problem 95

In Part I, we studied a monthly procurement problem, both theoretically and numerically. Part II is theoretical and more general.

In Chapter 8, we propose a more general model for the crude oil procurement than that developed in Part I, that spans an arbitrary number of months. We then build a corresponding multistage stochastic optimization problem. That problem has the particularity to feature two concurrent time scales; crude oil purchases are made every week while crude oil consumption is set once a month. We then build a unified timeline, propose a state variable, and reformulate the optimization problem as a stochastic optimal control problem.

In Chapter 9, we first introduce the notion of time block and time block state reduction, that is, the ability to express a state variable in only a subset of stages in the problem. We then apply this notion to problems featuring a slow and a fast time scale to write a dynamic programming equation at the slow time scale, namely, the crude oil procurement as formalized in Chapter 8. One key point of this time decomposition is that it does not require any assumption on the fast scale noises, only independence from one slow scale to the other. The content of this chapter has been submitted as a paper.

97

Chapter 8

General procurement optimization problem formulation 8.1 Introduction

In this Chapter 8, we tackle any number of months for the refinery operation and we handle crude quality issues.

In §8.2, we present modeling elements that make it possible to write multistage stochastic optimization problems. Then, in §8.3, we provide an optimal control reformulation.

General monthly deliveries model

In this section, we provide all the elements needed to write a multistage stochastic optimization problem. More precisely, §8.2.1.1, §8.2.1.2 and §8.2.1.3 are steppingstones in which we describe the representations of oil and time. Then, in §8.2.1.4 we introduce the control variables. In §8.2.2, we introduce the various expressions that will constitute the optimization problem such as the dynamics and the cost functions. Nonanticipativity constraints are detailed in §8.2.2.5 as they constitute one of the particularities of the studied problem. All the elements introduced before are combined in §8.2.3 to produce a multistage stochastic optimization problem.

Procurement model characteristics

In this section, we introduce the modeling elements for the general procurement of crude oil. Precisely, in §8.2.1.1 we introduce the notations used for the new description of crude oil shipments. In §8.2.1.2, we introduce notations for time and in §8.2.1.3, relations to link purchase weeks and delivery months. Finally, in §8.2.1.4, we present the decisions variables we consider in this procurement problem.

Oil characteristics

We summarize in Table 8.1 the notations used for oil characteristics. notation set meaning C finite set of crudes on the market

V c ⊂ R + volume of crude c α ∈ N * number of characteristics of a crude Q c ⊂ R α quality vector of crude c π c V : c ′ ∈C (V c ′ × Q c ′ ) → V c projector to volume of crude c π c Q : c ′ ∈C (V c ′ × Q c ) → Q c projector to quality of crude c π V : c ′ ∈C (V c × Q c ) → c∈C V c projector to volumes π Q : c∈C (V c × Q c ) → c∈C Q c projector to qualities π c : c ′ ∈C (V c ′ × Q c ′ ) → (V c × Q c )
projector to a single crude Table 8.1: Oil characteristics notations Crude oil is the main resource TotalEnergies uses and purchases. Many crudes exist and are available on the market as we introduced in Chapter 3. In Part I, crudes were only described by a volume according to the modeling elements from Chapter 3. In this Chapter 8 however, we explicit the characteristics of each crude oil.

We usually refer to the characteristics of a crude oil as its quality. This quality differs from crude to crude but also from cargo to cargo. For instance, the quality of the crude oil coming from the Ekofisk field, and labeled as B5, varies in time. The causes for such variations are multiple. The composition of an hydrocarbon reservoir is not homogeneous and therefore, the composition of the oil that is extracted changes, as the oil well is drained. Additionally, certain chemical components like iron and sulfur can mix with oil during the extraction or the shipping process and taint the oil. We denote by

Q c ∈ Q c ⊂ R α , (8.1a)
the quality of the crude c being considered. More precisely, the quality Q c is given by a vector of reals of size α. The components of the vector can be:

the various concentration in certain foreign chemical elements (e.g sulfur, iron), the chemical composition of the oil (e.g saturated/ aromatic hydrocarbon weight%), the physical properties of the crude oil (e.g density, ebullition temperature), TotalEnergies custom indicators giving the average yields for a specific refinery.

Additionally, we denote by

V c ∈ V c ⊂ G (8.1b)
the volume in barrels (bbl) of crude c in a cargo where G is the set of existing tankers capacities introduced in §3.3.1.2. Given that tankers only come in few sizes, the volume V c of crude oil has to comply with the limitations imposed by the standardized tanker sizes. Finally, for a given crude c, not all cargo sizes will be possible. As an example, the biggest tankers are too large to cross the Suez canal. As a result, no crude from Somalia will be available in volumes larger than 200.000 bbl, hence V c ⊂ G.

A cargo of crude oil c is therefore described by a couple in the product space

V c × Q c .

Time discretization

We summarize in Table 8 As introduced in §3.3.1.1, we denote by M the set of consecutive months we want to run the refinery for. We also denote by W the set of weeks in a month.

Similarly to what is done with (3.2) in §3.3.1.1, M and W are fitted with a total order:

min M = m ⪯ • • • ⪯ m --⪯ m -⪯ m ⪯ m + ⪯ m ++ ⪯ • • • ⪯ m = max M , (8.2a) min W = w ⪯ • • • ⪯ w --⪯ w -⪯ w ⪯ w + ⪯ w ++ ⪯ • • • ⪯ w = max W . (8.2b)
We denote by m + the successor of m and m ++ its double successor (i.e the successor of m + ). Then we build the same product space M × W as in §3.3.1.1, fitted with the same lexicographical order introduced in (3.3):

(m, w) ⇝ • • • ⇝ (m, w) ⇝ (m, w + ) ⇝ • • • ⇝ (m, w) ⇝ (m + , w) ⇝ • • • ⇝ (m, w) .
In the chain M × W, a successor is defined by In Part I, crudes are only available to purchase up to 2 months / 8 weeks in advance of their delivery month. This means orders for a delivery in December will run in October and November. In this model, we relax this specification and introduce the relation P ⊂ (M × W) × M which defines a correspondence P by

(m, w) + = (m, w + ) if w ≺ w , (m + , w) if w = w , ∀(m, w) ∈ M × W . ( 8
∀(m, w) ∈ M × W, ∀m ′ ∈ M, (m, w)Pm ′ ⇐⇒ ((m, w), m ′ ) ∈ P . (8.3a)
When (m, w)Pm ′ , we say that (m, w) is a purchase week for the months m ′ ; it is possible to purchase crude oil in week (m, w). This crude will arrive at the beginning of month m ′ .

For each month m ′ ∈ M, we write the set of corresponding purchase stages

Pm ′ = {(m, w) ∈ M × W | (m, w)Pm ′ } , ∀m ′ ∈ M . (8.3b) Similarly, (m, w)P = {m ′ ∈ M | (m, w)Pm ′ } (8.3c)
is the set of months related to the purchase stage (m, w).

Then, we introduce the relation

P ⊂ (M × W) × M defined by (m, w)Pm ′ ⇐⇒ (m, w) ∈ [inf Pm ′ , (m ′ , w)[ . (8.3d)
The week (m, w) is in relation with m ′ through P if it sits between the first week of purchase for the month m ′ and the beginning of that month m ′ . The relation P can be seen as an extension of P; (m, w)Pm ′ if the week (m, w) is positioned after the first purchase opportunity for the month m ′ and before the beginning of the month m ′ . Therefore, Pm ′ represents all the weeks during which a crude has potentially already been ordered for the month m ′ but is yet to be delivered.

Decisions

In this problem we consider only two kinds of decisions (controls): the purchase of crude oil and the consumption of crude oil.

Crude oil purchase. We summarize in Table 8.4 the notations used for oil purchase.

We denote by

b m ′ ,c (m,w) ∈ B m ′ ,c (m,w) ⊂ V c × Q c , (8.4a)
the cargo purchased at week (m, w) that will be delivered at the beginning of month m ′ . Contrarily to Part I, the quality of the crude is included in the control. This reflects the notion that the decision maker chooses a specific cargo, characterized by both its volume and quality. Additionally, it is impossible to choose quantity independently of quality and the set Crude oil consumption. We summarize in Table 8.5 the notation used for oil consumption inside the refinery. the crude oil consumption in the refinery we set for the month m. It is a vector of quantities. Although crude oil is not the only resource that is being consumed by a refinery during production, it is the resource we focus on and the only one we chose to display. During production, a refinery can choose to import (or export) intermediate products. We make the choice to count these importations as part of the production costs.

B m ′ ,c (m,w) of available cargo is a finite subset of V c × Q c . By extension, we denote by b m ′ (m,w) ∈ B m ′ (m,w) = c∈C B m ′ ,c (m,w) ⊂ c∈C (V c × Q c ) , ( 8
Refinery settings. We summarize in Table 8.6 the notations used for the settings of the refinery. We denote by r m the settings used to run the refinery during stage m. These settings correspond to the settings briefly presented in §6.2, and are the collection of all the settings for all the units inside the refinery. We will denote by

R m = u∈U R u m , (8.6)
the space of the settings for the month m. The nature of each R u m depends on the unit u it is referring to. These settings can be the various temperatures set for distillation inside the refinery or mixing rates for CO 2 or H 2 in the hydrodesulfurization unit. Optimization of a refinery's configuration is a complex topic in its own right.

Building blocks of an optimization problem

In §8.2.1, we introduced the modeling elements of the general procurement problem that differ from the models built in Chapter 3. Now, we introduce the remaining elements that will make it possible to write an optimization problem.

Dynamics of delivery buffers and oil stock

We model the accumulation of orders, deliveries and consumptions with stocks. There are two kind of stocks in the problem:

Buffers are virtual stocks that model the accumulation of orders for a single delivery stage. We call m-buffer the buffer that will empty (be delivered) at the beginning of month m. By construction, the m-buffer has a limited lifespan: it appears at the first purchase week related to m, that is, in week infPm, and disappears at the beginning of month m.

The main stock is the physical stock of all the crudes stored in the refinery. The main stock is impacted by the monthly consumption of crude oil and the crude deliveries. The buffers are added to the main stock at their respective delivery stages.

We summarize in Table 8.7 the notations used for the buffers and the main stock. variable set meaning

s m c∈C (R + × Q c
) main stock at the begining of the month m

d m ′ (m,w) c∈C (V c × Q c
) stock in the m ′ -buffer at the beginning of the week (m, w) Thus we have that:

Pm ′ is the lifespan of the m ′ -buffer, (m, w)P is the set of months for which (m, w) is in the lifespan of the associated buffer.

The time evolution of the stock in the m ′ -buffer follows the following dynamic equation

d m ′ (m,w) + = F m ′ (m,w) (d m ′ (m,w) , b m ′ (m,w) ) , ∀((m, w), m ′ ) ∈ P , (8.7b)
with the initialization

d m ′ min Pm ′ = 0 . (8.7c)
Although F m ′ (m,w) is defined for every week the m ′ -buffer exists (i.e for (m, week) ∈ Pm ′ ), the buffer is only modified when oil can be purchased (i.e for (m, w) ∈ Pm ′ ).

If not cargo can be purchased, then the m ′ -buffer stays the same and we have:

F m ′ (m,w) (d m ′ (m,w) , b m ′ (m,w) ) = d m ′ (m,w) , ∀(m, w) ∈ Pm ′ \ Pm ′ . (8.7d)
As a result, d m ′ (m,w) can also be expressed as a function of past purchases,

d m ′ (m,w) = F m ′ (m,w) {b m ′ (m ′′ ,w ′′ ) } (m ′′ ,w ′′ )∈Pm ′ (m ′′ ,w ′′ )≺(m,w)
, ∀((m, w), m ′ ) ∈ P . (8.7e)

The functions F m ′ (m,w) and F m ′ (m,w) model the mixing of qualities for crudes with different qualities and thus do not have reasonable extensive expression. However, the volumes of crudes remain additive and, using the volume projector π V introduced in Table 8.1, we can write:

π V (d m ′ (m,w) + ) = π V (d m ′ (m,w) ) + 1 (m,w)∈Pm ′ π V (b m ′ (m,w) ) , ∀(m, w) ∈ Pm ′ . (8.7f)
Main stock. We denote by s m the crude oil stocks in the refinery at the beginning of the month m. The time evolution of the refinery is given by the dynamic equation

s m + = F m (s m , d m (m,w) , u s m ) , ∀m ∈ M , (8.8a)
with the initial step

s m + = F m (s m , d m (m,w) , u s m ) , ∀m ∈ M , (8.8b)
with:

s m , the initial stock, being part of the data of the problem, u s m is the part of the stocks consumed throughout the month m, d m (m,w) is the m-buffer that is added to the stock at the start of the month m. As a result, s m can also be expressed as a function of past buffers and consumptions

s m = F m {d m (m ′ ,w) } m ′ ≺m , {u s m ′ } m ′ ≺m , ∀m ∈ M . (8.8c)
As for the buffers, we will not seek an extensive formula for F m , as the function models the blending of crude oil qualities, which is too complex. However, we can express the dynamics of the volumes for one month m to the next using the volume projectors π V introduced in Table 8.1

π V (s m + ) = π V (s m ) + π V (d m (m,w) ) -u s m , ∀m ∈ M . (8.8d)

Economic uncertainties

At this point in the study, we consider that the only source of uncertainty in the procurement process lies in the prices. These fall into two categories, the primes of the crudes that can be purchased and the prices of the products that are sold on the market.

Crude oil premiums. We summarize in Table 8

w c (m,w) ∈ W c (m,w) ⊂ R , (8.9a)
the market prime per volume unit of the crude c in week (m, w) and by

w (m,w) = (w c (m,w) ) c∈C ∈ W (m,w) = c∈C W c (m,w) , (8.9b)
the corresponding vector for all crudes. This uncertainty is revealed to the decision maker just before he decides of the crudes to buy (b m ′ (m,w) ) m ′ ∈(m,w)P .

Products prices. We summarize in Table 8.9 the notations relative to the sales of finished products. selling price space of all products during the month m p m P m selling prices of all products during the month m Table 8.9: Selling prices

The refinery turns crude oil into products that are subsequently sold on the market. We denote by From an industrial perspective, the products that are sold by the refinery are not necessarily finished products. Some exportation streams can be intermediate products that are only partially consumed by the refinery. In the future, the quality of the products sold will depend on their quality. At this moment, p p m will be regarded as the reference price for product p on which the actual selling price will be indexed. p p m is discovered just before deciding the control u s m .

p p m ∈ P p m ⊂ R + , ( 8

Cost functions

We summarize in Table 8.10 the economic functions relative to the purchase of crude oil and the exploitation of the refinery. Purchase costs. The quantity

(m,w)∈M×W m ′ ∈(m,w)P Ω m ′ (m,w) (d m ′ (m,w) , b m ′ (m,w) , w (m,w) )
is the total amount spent on purchases. Here, Ω m ′ (m,w) is a generalization of the function introduced in the monthly procurement problem in (3.11c).

Production costs and earnings. The quantity

m∈M Ψ m (s m , d m (m,w) , u s m , r m , p m )
is the total operation costs (i.e cost to run the refinery -earnings from sales) over the months M. The function Ψ m is the production function of the refinery for the interval [m, m + ]. This function Ψ m is a generalization of the production function used for the monthly procurement problem and introduced in (3.16). Here, we assume direct control over the consumption and the settings of the refinery. The variable d m (m,w) represents the state of the m-buffer at the beginning of the month m, that is, the crude delivered to the refinery at the beginning of the month m ′ .

Bound constraints

We divide constraints into two categories: those that only concern a single variable and those that concern several variables. notation space meaning

U s m ⊂ c∈C V c set of possible consumptions during the month m S m ⊂ c∈C (V c × Q c )
set of acceptable stocks levels in the refinery Processing limitations inside the refinery. We denote by U s m the set of crudes quantities that can be consumed in the refinery during the month m. The set U s m is finite. An admissible consumption therefore satisfies the constraint

D m ⊂ c∈C (V c × Q c )
u s m ∈ U s m ⊂ c∈C V c . (8.12)
The set U s m takes into account the physical limitations of the refinery such as minimum and maximum processing capacities of the units inside the refinery. Additionally, the set of admissible consumptions is designed so that products output constraints are respected.

Crudes inside the refinery. The refinery has a limited crude storage capacity, which cannot be exceeded. Similarly, there are minimum stock levels the refinery cannot afford to go below. Therefore, there are constraints on the stock inside the refinery of the form

s m ∈ S m ⊂ c∈C (V c × Q c ) , ∀m ∈ M . (8.13)
Delivery constraints. Docking constraints put limitations on the amounts of crude that can be delivered each month. We formulate this constraint as a constraint on each buffer by means of a subset D m as follows:

d m (m,w) ∈ D m ⊂ c∈C (V c × Q c ) , ∀m ∈ M . (8.14)

Nonanticipativity constraints

We write down the information structure of the uncertainties and the controls as follows

• • • ⇝ p m ⇝ (u s m , r m ) ⇝ w (m,w) ⇝ assuming(m,w)P̸ =∅, else, no such decision exists {b m ′ (m,w) } m ′ ∈(m,w)P ⇝ ⇝ w (m,w) + ⇝ {b m ′ (m,w) + } m ′ ∈(m,w) + P ⇝ • • • ⇝ w (m,w) ⇝ {b m ′ (m,w) } m ′ ∈(m,w)P ⇝ p m + ⇝ • • •
This leads to expressing the nonanticipativity constraint of both types of controls, the purchase decisions first and then the consumption/settings decisions as follows

σ()b m ′ (m,w) ] ⊂ σ({p m ′′ } m ′′ ⪯m , {w (m ′′ ,w ′′ ) } (m ′′ ,w ′′ )⪯(m,w) ) , (8.16
)

σ(u s m , r m ) ⊂ σ({p m ′′ } m ′′ ⪯m , {w (m ′′ ,w ′′ ) } (m ′′ ,w ′′ )≺(m,w) ) . (8.17)
We already stated that b m ′ (m,w) is taken in reaction to the past crude oil premiums w (m,w) . The decisions u s m and r m is taken in reaction to the past of the product prices p m , but without the knowledge of the next crude premiums w (m,w) yet.

Optimization problem

With all the modeling elements introduced previously, we write a first optimization problem as follows:

min {b m ′ (m,w) } ((m,w),m ′ )∈P {u s m ,r m } m∈M E (m,w)∈M×W m ′ ∈(m,w)P Ω m ′ (m,w) (d m ′ (m,w) , b m ′ (m,w) , w (m,w) ) (8.18a) + m∈M Ψ m (s m , d m (m,w) , u s m , r m , p m ) constraints on decisions b m ′ (m,w) ∈ B m ′ (m,w) , ∀m ′ ∈ M , ∀(m, w) ∈ Pm ′ (8.18b) u s m ∈ U s m , ∀m ∈ M (8.18c) r m ∈ R m , ∀m ∈ M (8.18d) constraints on stocks d m (m,w) ∈ D m , ∀m ∈ M (8.18e) s m ∈ S m , ∀m ∈ M (8.18f)
dynamics on the stocks

d m min Pm = 0 , ∀m ∈ M (8.18g) d m ′ (m,w) + = F m ′ (m,w) (d m ′ (m,w) , b m ′ (m,w) ) , ∀((m, w), m ′ ) ∈ P , (8.18h)
s m + = F m (s m , d m (m,w) , u s m ) , ∀m ∈ M , (8.18i)
nonanticipativity constraints

σ(b m ′ (m,w) ) ⊂ σ({p m ′′ } m ′′ ⪯m , {w (m ′′ ,w ′′ ) } (m ′′ ,w ′′ )⪯(m,w) ) , (8.18j)
σ(u s m , r m ) ⊂ σ({p m ′′ } m ′′ ⪯m , {w (m ′′ ,w ′′ ) } (m ′′ ,w ′′ )≺(m,w) ) . (8.18k)
In Problem (8.18), bold variables represent random variables. w (m,w) and p m naturally are random variables as they are the sources of uncertainty in the problem. The decision variables b (m,w) , u s m and r m also are random variables since, according to nonanticipativity constraints (8.18j) and (8.18k), they are functions of the past uncertainties. Right now, Problem (8.18) is not in the usual form of multistage stochastic optimization problems as all variables do not belong to the same time scale. Additionally, there is no clear state nor dynamic in this problem. In the following section §8.3, we reformulate the problem (8.18) as a proper stochastic optimal control problem.

Stochastic optimal control reformulation

In this section we present a reformulation of the Problem 8.18 presented above into a stochastic optimal control problem. More precisely, in §8.3.1, we adopt a unified timeline for all controls and uncertainties in , propose a state variable in §8.3.2.

Mathematical reformulation of the optimization problem

The purpose behind reformulating Problem (8.18) is to be able to write a dynamic programming equation. To that end, we first need to have a unified timeline for controls and uncertainties. We add a fictitious week index w preceding any week w ∈ W and we denote this new extended set by

W = { w} ∪ W . (8.19a)
Since W, as defined in §8.2.1.2, is a chain, W is one too with the total order .19b) We now introduce the extended time span T defined by

w ≺ min W = w ⪯ • • • ⪯ w --⪯ w -⪯ w ⪯ w + ⪯ w ++ ⪯ • • • ⪯ w = max W . ( 8
T = M × W . (8.19c)
Similarly to what was done in §8.2.1.2, we also define a lexicographical order on T by

(m, w) ≺ (m, w) ≺ • • • ≺ (m, w) ≺ (m, w + ) ≺ • • • (8.19d) • • • ≺ (m, w) ≺ (m + , w) ≺ (m + , w) ≺ • • • (8.19e) • • • ≺ (m, w -) ≺ (m, w) , (8.19f)
with a successor written as

(m, w) + = (m + , w) if w = w (m, w + ) if w ≺ w . (8.19g)
The chronology of controls and uncertainties now writes

• • • ⇝ p (m, w) ⇝ (u s (m, w) , r (m, w) ) ⇝ w (m,w) ⇝ {b m ′ (m,w) } m ′ ∈(m,w)P ⇝ ⇝ w (m,w) + ⇝ {b m ′ (m,w) + } m ′ ∈(m,w) + P ⇝ • • • ⇝ w (m,w) ⇝ {b m ′ (m,w) } m ′ ∈(m,w)P ⇝ p (m + , w) ⇝ • • • ,
where the monthly decisions and uncertainties for the month m are slotted in the fictitious step (m, w), at the very beginning of the month and, we have

p (m, w) = p m , ∀m ∈ M , (8.20a)
(u s (m, w) , r (m, w) ) = (u s m , r m ) , ∀m ∈ M . (8.20b)
At this point, we now have a unified timeline where have slotted the monthly decisions and uncertainties at the beginning of each month, in a fictitious step. In doing so, we also clarify the interdependency between controls and uncertainties. It now clearly appears that the consumption decision u s (m, w) and the settings of the refinery r (m, w) are taken in reaction to the revelation of product prices p (m, w) but without the yet knowing of premiums w (m,w) for the first week of the month m.

Controls and uncertainties

Controls. In the Table 8 As a consequence of introducing the fictitious step w at the beginning of each month m, we need to review the relations P and P introduced in §8.2.1.3.

The relation P ⊂ (M × W) × M, defined in (8.3a), induces a binary relation O ⊂ T × T defined by tOt ′ ⇐⇒ ∃m ∈ M, t ′ = (m, w) , t ∈ T and tPm .

(8.21a)

Additionally, we define a new binary relation O ⊂ T × T, that mirrors P, defined in (8.3d), by

tOt ′ ⇐⇒ ∃m ∈ M, t ′ = (m, w) and ∃t ′′ ≺ t| t ′′ Ot ′ . (8.21b)
As a result, the stages (m, w) only appear in the relation O as targets stages for which it is possible to order, but during which no purchase can be made. Yet, the relation P ensures that buffers continue to exist during the fictitious stage (m, w).

In Problem (8.18), controls are twofold:

the purchase decision b m ′ (m,w) has a delayed effect, targets a future month m' and does not exist for all ((m, w), m ′ ), only the couples in correspondance through P, the operation decisions u s m (crude consumption) and r m (refinery settings) are instantaneous.

We adopt a single notation for the controls

u t = u s (m, w) , r (m, w) ∈ R |C| + × R if t = (m, w) {u m ′ (m,w) } m ′ ∈(m,w)P ∈ R |C|×|tP| if t = (m, w) ∈ M × W , ∀t ∈ T .
(8.22a) The variables u s m , r m and u m ′ (m,w) are the decision variables identified in §8.2.1.4. They respectively correspond to the crude oil consumption in month m, the settings of the refinery for the the month m, and the crude oil purchases in week (m, w) that will be delivered at the beginning of the month m ′ .

What makes this problem singular is that, as a result of aligning all the decisions variables on the same timeline in (8.22a), the dimension of the control u varies every step. If t corresponds to a stage (m, w), then u t ∈ R |C| + × R. If t corresponds to a week, that is, t = (m, w) with w ≻ w, then u t ∈ R |C|×|tO| . For ease of use, we adopt the notation

u t = {u m ′ t } m ′ ∈tP = {u m ′ t } m ′ ∈tP if t ∈ M × W . (8.22b)
Uncertainties. The remarks on controls also apply to uncertainties. Due to the unified timeline, the dimension of the uncertainties varies from step to step. On the one hand, if t = (m, w), then the uncertainty is the vector of product prices p (m, w) ∈ R |P| ; its dimension is the number of products sold by the refinery. On the other hand, if t = (m, w) ∈ M × W and thus corresponds to an actual week, then the uncertainty w (m,w) ∈ R |C| is the vector of crude premiums; its dimension is |C|, the number of crudes on the market. Similarly to controls, we adopt the notation

w t = p m ∈ R |P| if t = (m, w) w (m,w) ∈ R |C| if t ∈ M × W , ∀t ∈ T . (8.23)
Nonanticipativity constraints. Along with a reformulation of the controls and the uncertainties in (8.22a) and (8.23), comes the reformulation of the nonanticipativity constraints (8.18j) and (8.18k) into the single constraint

σ(u t ) ⊂ σ({w t ′ } t ′ ≺t ) . (8.24)

Stocks and dynamics

In this section, we come back to the stocks and buffers introduced in §8.2.2.1 and adapt them to the single timeline T introduced in (8.19c).

Buffers We now extend the definition (8.7e) of buffers as well as their dynamic (8.7b). Using the relations O and O in §8.21, we introduce the t ′ -buffer defined by its dynamic equation

d t ′ t + = F t ′ t (d t ′ t , u t ′ t ) , ∀t ′ ∈ M , ∀t ∈ Ot ′ , (8.25a)
with

F t t (d t ′ t , u t ′ t ) = F m ′ (m,w) (d t ′ t , u t ′ t ) , if t ′ = (m ′ , w) , t = (m, w) , tOt ′ , d t ′ t , if t ̸ ∈ Ot ′ . (8.25b)
Where F m ′ (m,w) is the buffer dynamic equation introduced in (8.7b). The t ′ -buffer d t ′ t is the virtual stock at the beginning of stage t that will be delivered and added to the stock of the refinery at the beginning of the stage t ′ ∈ M × { w}. Since t ′ is a fictitious stage added in (8.19a), we identify this buffer to the m ′ -buffer defined in (8.7e) for t ′ = (m ′ , w) by

d t ′ t = d m ′ (m,w) , ∀t = (m, w) ∈ M × W , t ′ = (m ′ , w) ∈ M × { w} . (8.26a)
Refinery stocks We now extend the definition of the stock s to all t ∈ T with the dynamic equation

s t + = F t (s t , d t t , u t )∀t ∈ T . (8.27a)
with

F t (s t , d t t , u t ) = F m (s t , d t t , u t ) , if t ∈ M × { w} s t , if t ∈ M × W . (8.27b)
Where F m is the refinery stocks dynamic equation introduced in (8.8a). As a result, the stock s t is updated once a month, during the step w, and stays constant otherwise

s t = s m , ∀t ∈ {m} × W , (8.27c)
The stock s inside the refinery is now defined for every step t ∈ T. The dynamic of the stock that was previously at the scale of the month in §8. In §8.2.2.3, we made the distinction between the cost of purchasing oil each week (m, w) through the functions Ω m ′ (m,w) , and the production costs of the refinery for each month m, the function Ψ m . Now, with the unified timeline T, all costs appear as instantaneous cost functions {Λ t } t∈ T , defined as:

Λ t (s t , {d t ′ t } t ′ ∈tO , u t , w t ) =        t ′ ∈tO t ′ =(m ′ , w) Ω m ′ (m,w) (d t ′ t , b t ′ t , w t ) if t = (m, w) ∈ M × W , Ψ m (s t , d t t , u s t , p t ) if t = (m, w) ∈ M × { w} , ∀t ∈ T .
(8.28)

Proposing a state

We now propose a family {x t } t∈ T of state variables given by

x t = x s t main stocks at stage t , {x t ′ t } t ′ ∈tO current stock of each buffer active at stage t ∈ X t , (8.29a)
with the identification

x s t = s t ∈ R |C| + , (8.29b)
x t ′ t = d t ′ t ∈ R |C| + , ∀t ′ ∈ tO , (8.29c)
with the dynamic

x t + = Ft (x t , u t ) , ∀t ∈ T . (8.29d)
where

Ft (x t , u t ) = F t (x s t , x t t , u t ), { F t ′ t (x t ′ t , u t ′ t )} t ′ ∈tO (8.29e)
Intuitively, the state at stage t contains the main stock s t as well as relevant buffers. The buffers d t ′ t contained in the state are those active at stage t, that is, elements of tO. The dynamic of the state variable x t written in (8.29d) is a compound function of both the main stock dynamics and buffers dynamics presented respectively in (8.27a) and (8.25a).

Stochastic optimal control problem

With all the elements introduced from §8.3.1 to §8.3.2, we now reformulate the problem (8.18) as a stochastic optimal control problem min

{u t } t∈ T {x t } t∈ T E {w t } t∈ T t∈ T Λ t x t , u t , w t (8.30a) u t ∈ U t , ∀t ∈ T , (8.30b)
x t ∈ X t , ∀t ∈ T , (8.30c)

x t + = Ft (x t , u t ) , ∀t ∈ T (8.30d) σ(u t ) ⊂ σ({w t ′ } t ′ ≺t ) , ∀t ∈ T . (8.30e)

Conclusion

In this Chapter 8, we have extended the modeling elements used in Part I to formulate a crude oil procurement problem over an arbitrary number of months. The two main features of this new model are the following: crude oil is now described by its quality as well as quantity; the model works for any number of operating months for the refinery. Specifically, in §8.2 we presented a model for the general procurement problem and then formulated a multistage stochastic optimization problem that we write as Problem (8.18). Then, in §8.3, we reformulated the Problem (8.18) to express it as a stochastic optimal control problem in Problem (8.30). This reformulation implies that, under an assumption of independence of noises, the problem can be solved using stochastic dynamic programming. While theoretically feasible, such a direct approach would likely not be numerically tractable given the size of the problem.

In the next Chapter 9, we present a framework that directly leverages the month/week structure of the Problem (8.18) to write more effective dynamic programming equations.

Chapter 9 Time blocks decomposition of multistage stochastic optimization problems 9.1 Introduction

Multistage stochastic optimization problems are, by essence, complex because their solutions are indexed both by stages (time) and by uncertainties. Their large scale nature makes decomposition methods appealing. The most common approaches are time decomposition (state-based resolution methods), like stochastic dynamic programming, in stochastic optimal control, and scenario decomposition, like progressive hedging, in stochastic programming. On the one hand, stochastic programming deals with an underlying random process taking a finite number of values, called scenarios [START_REF] Shapiro | Lectures on stochastic programming: modeling and theory. The society for industrial and applied mathematics and the mathematical programming society[END_REF]. Solutions are indexed by a scenario tree, the size of which increases exponentially with the number of stages (hence generally a few stages in practice). However, to overcome this obstacle, stochastic programming takes advantage of scenario decomposition methods (progressive hedging [START_REF] Rockafellar | Scenarios and policy aggregation in optimization under uncertainty[END_REF]). On the other hand, stochastic control deals with a state model driven by a white noise, that is, the noise is made of a sequence of independent random variables. Under such assumptions, stochastic dynamic programming is able to handle many stages, as it offers reduction of the search for a solution among state feedbacks (instead of functions of the past noise) [START_REF] Bellman | Dynamic Programming[END_REF][START_REF] Puterman | Markov Decision Processes[END_REF].

In a word, dynamic programming is good at handling multiple stages -but at the price of assuming that noises are stagewise independent -whereas stochastic programming does not require such assumption, but can only handle a few stages. Could we take advantage of both methods? Is there a way to apply stochastic dynamic programming at a slow time scale -a scale at which noise would be statistically independent -crossing over fast time scale optimization problems where independence would not hold? This question is one of the motivations of this paper, and we indeed provide a method to decompose multistage stochastic optimization problems by time blocks. This decomposition method and the main result are, mathematically speaking, quite natural, but the main difficulty is notational. Indeed, the rigorous formulation of multistage stochastic optimization problems on so-called history spaces requires heavy notation.

The methodology developed in this paper has been successfully applied to a multistage stochastic optimization problem involving several hundred thousand time steps, namely a battery management problem over 20 years involving both the battery operating (with a fast time step of 30 minutes) and the battery replacement (with a slow time step of one day) [START_REF] Rigaut | Time Decomposition Methods For Optimal Management Of Energy Storage Under Stochasticity[END_REF]. It is assumed that the vectors of noises (energy demand minus renewable energy production) are independent day by day, so that we are able to write the Dynamic Programming equations at the slow time scale for this two time scales optimization problem. Then we use decomposition techniques to obtain lower and upper bounds for the Bellman value functions: the corresponding approximated value functions are also computed by backward recursion, involving intraday costs (fast time scale) which are computable offline. Finally, taking into account some periodicity properties in the computation of intraday costs allows to solve the problem using a reasonable CPU time.

The paper is organized as follows. In Sect. 9.2, we present the standard approaches to solve, by dynamic programming, a stochastic optimal control problem formulated in discrete time. In Sect. 9.3, we revisit the notion of "state" by defining state reduction by time blocks -that is, at stages that are not necessarily all the original stages -and then we prove a reduced dynamic programming equation. In Sect. 9.4, we illustrate our contribution by showing its potential for applied problems with two time scales, as the crude oil procurement problem. We relegate technical results in Appendix A.

Stochastic dynamic programming with histories

In §9.2.1, we recall standard approaches to solve, by dynamic programming, a stochastic optimal control problem formulated in discrete time. We emphasize that, in all of these approaches, either a state is given for all times or no state is given. We highlight that our approach is intermediate, in that a state will possibly be obtained, but only at certain times. In §9.2.2, we formulate multistage stochastic optimization problems over the so-called history space, with history feedbacks, and we obtain a general dynamic programming equation.

Background on stochastic dynamic programming

We first recall the notion of stochastic kernel, used in the modeling of stochastic control problems. Let (X, X) and (Y, Y) be two measurable spaces. A stochastic kernel from (X, X) to (Y, Y) is a function ρ : X×Y → [0, 1] such that, for any Y ∈ Y, the function ρ(•, Y ) : X → [0, 1] is X-measurable and, for any x ∈ X, the function ρ(x, •) : Y → [0, 1] is a probability measure. By a slight abuse of notation, a stochastic kernel is also denoted as a mapping ρ : X → ∆(Y) from the measurable space (X, X) towards the space ∆(Y) of probability measures over (Y, Y), with the property that the function x ∈ X → Y ρ( dy | x) is measurable for any Y ∈ Y.

We now sketch the most classical frameworks for stochastic dynamic programming in discrete time. We use the notation r, s = {r, r + 1, . . . , s -1, s} for any two integers r, s such that r ≤ s. We will also use the shorter notation r:s = r, s , for example in subscripts as in h r:s . In what follows, t 0 ∈ N and T ∈ N * are two integers such that t 0 < T .

Witsenhausen approach

The most general stochastic dynamic programming principle is sketched by Witsenhausen at the end of [START_REF] Witsenhausen | On policy independence of conditional expectations[END_REF]. However, we do not detail it as its formalism is too far from the following ones, though we will touch the subject when we discuss Yüksel's approach below. We present here what Witsenhausen calls an optimal stochastic control problem in standard form (see [START_REF] Witsenhausen | A standard form for sequential stochastic control[END_REF]). The ingredients are the following:

1. time t ∈ t 0 , T is discrete and runs among a finite set of consecutive integers; 2. (X t 0 , X t 0 ) (Nature), (X t 0 +1 , X t 0 +1 ), . . . , (X T , X T ) (state spaces) are measurable spaces;

3. (U t 0 , U t 0 ),. . . , (U T -1 , U T -1 ) are measurable spaces (control spaces);

4. I t is a subfield of X t , for t ∈ t 0 , T -1 (information);

5. f t : (X t × U t , X t ⊗ U t ) → (X t+1 , X t+1 ) is measurable, for t ∈ t 0 , T -1 (dynamics); 6. π t 0 is a probability on (X t 0 , X t 0 ); 7. j : (X T , X T ) → R is a measurable function (criterion).
With these ingredients, Witsenhausen formulates a stochastic optimization problem, whose solutions are to be searched among adapted feedbacks, namely λ t : (X t , X t ) → (U t , U t ) with the property that λ -1 t (U t ) ⊂ I t for all t ∈ t 0 , T -1 . Then, he establishes a dynamic programming equation, where the Bellman functions are function of the (unconditional) distribution of the original state x t ∈ X t , and where the minimization is done over adapted feedbacks. The main objective of Witsenhausen is to establish a dynamic programming equation for nonclassical information patterns.

Evstigneev approach

The ingredients of the approach developed in [START_REF] Evstigneev | Measurable selection and dynamic programming[END_REF] are the following:

1. time t ∈ t 0 , T is discrete and runs among a finite set of consecutive integers; 2. (U t 0 , U t 0 ),. . . , (U T -1 , U T -1 ) are measurable spaces (control spaces); 3. (Ω, F) is a measurable space (Nature); 4. {F t } t∈ t 0 ,T -1 is a filtration of F (information); 5. P is a probability on (Ω, F);

6. j : (Ω × t∈ t 0 ,T -1 U t , F ⊗ t∈ t 0 ,T -1 U t ) → R is a measurable function (criterion).
With these ingredients, Evstigneev formulates a stochastic optimization problem, whose solutions are to be searched among adapted processes, namely random processes with values in t∈ t 0 ,T -1 U t and adapted to the filtration {F t } t∈ t 0 ,T -1 .

Then, he establishes a dynamic programming equation, where the Bellman function at time t is an F t -integrand depending on controls up to time t (random variables) and where the minimization is done over F t -measurable random variables at time t. The main objective of Evstigneev is to establish an existence theorem for an optimal adapted process (under proper technical assumptions, especially on the objective function j, that we do not detail here). Notice that there is no notion of state variable.

Puterman approach

The ingredients of the approach developed in [32, Sect. 2.1] are the following:

1. time t ∈ t 0 , T is discrete and runs among a finite set of consecutive integers;

2. (X t 0 , X t 0 ), . . . , (X T , X T ) are measurable spaces (state spaces); With these ingredients, Hernández-Lerma and Lasserre formulate a stochastic optimization problem with a time additive cost function over given state and control spaces. They introduce the "canonical construction" where the history at time t consists in the states and the controls prior to t. Then, they study optimization problems whose solutions (policies) are to be searched among history feedbacks (or randomized history feedbacks), namely sequences of mappings X t 0 × t-1 s=t 0 (U s × X s+1 ) → U t . They identify cases where no loss of optimality results from reducing the search to (relaxed) Markovian feedbacks X t → U t . Then, they establish a dynamic programming equation, where the Bellman functions are function of the state x t ∈ X t , and where the minimization is done over controls u t ∈ U t . For finite horizon problems, the mathematical challenge is to set up a mathematical framework -the Borel assumptions plus additional topological ones presented in [17, §3.3] -for which optimal policies exists. The main objective of [START_REF] Hernández | Discrete-Time Markov Control Processes: Basic Optimality Criteria[END_REF] is to offer a unified and comprehensive treatment of discrete-time Markov control processes, with emphasis on the case of Borel state and control spaces, and possibly unbounded costs and noncompact control constraint sets.

Bertsekas and Shreve approach The ingredients of the approach developed in [START_REF] Bertsekas | Stochastic Optimal Control: The Discrete-Time Case[END_REF] (more precisely in [START_REF] Bertsekas | Stochastic Optimal Control: The Discrete-Time Case[END_REF]Definition 10.1]) are the following:

1. time t ∈ t 0 , T is discrete and runs among a finite set of consecutive integers; 2. (X t 0 , X t 0 ), . . . , (X T , X T ) are Borel spaces (state spaces); 3. (U t 0 , U t 0 ),. . . , (U T -1 , U T -1 ) are Borel spaces (control spaces); there are also feasible state-dependent control constraints that we do not present here;

4. (W t 0 , W t 0 ),. . . , (W T , W T ) are Borel spaces (noise); With these ingredients, Bertsekas and Shreve formulate a stochastic optimization problem with a time additive cost function over given state spaces, control spaces and uncertainty spaces. They introduce the notion of history at time t which consists in the states and the controls prior to t and study optimization problems whose solutions (policies) are to be searched among history feedbacks (or relaxed history feedbacks), namely sequences of mappings X t 0 × t-1 s=t 0 (U s × X s+1 ) → U t . They identify cases where no loss of optimality results from reducing the search to (relaxed) Markovian feedbacks X t → U t . Then, they establish a dynamic programming equation, where the Bellman functions are function of the state x t ∈ X t , and where the minimization is done over controls u t ∈ U t . For finite horizon problems, the mathematical challenge is to set up a mathematical framework (the Borel assumptions) for which optimal policies exists. The main objective of Bertsekas and Shreve is to state conditions under which the dynamic programming equation is mathematically sound, namely with universally measurable Bellman functions and with universally measurable relaxed control strategies in the context of Borel spaces. The interested reader will find all the subtleties about Borel spaces and universally measurable concepts in [START_REF] Bertsekas | Stochastic Optimal Control: The Discrete-Time Case[END_REF]Chapter 7].

5. f t : (X t × U t × W t , X t ⊗ U t ⊗ W t ) → (X t+1 , X t+1 ),
Yüksel approach As said at the beginning, the most general stochastic dynamic programming principle is sketched by Witsenhausen at the end of [START_REF] Witsenhausen | On policy independence of conditional expectations[END_REF]. This approach builds upon the so-called Witsenhausen intrinsic model [START_REF] Witsenhausen | The intrinsic model for discrete stochastic control: Some open problems[END_REF] which does not consider state, but information under the form of σ-fields (see [START_REF] Witsenhausen | Equivalent stochastic control problems[END_REF] for the functional form). In [START_REF] Witsenhausen | A standard form for sequential stochastic control[END_REF], Witsenhausen provides conditions to express stochastic control optimization problems -with information constraints, but without state -in standard form with a state (the first approach that we have considered above).

Although Witsenhausen established a dynamic programming equation in [START_REF] Witsenhausen | A standard form for sequential stochastic control[END_REF], Yüksel notes in [START_REF] Yüksel | A universal dynamic program and refined existence results for decentralized stochastic control[END_REF] that "Witsenhausen's construction [. . . ] does not address the well-posedness of such a dynamic program" and that "the existence problem was not considered". In the spirit of [START_REF] Witsenhausen | A standard form for sequential stochastic control[END_REF], Yüksel entails in [START_REF] Yüksel | A universal dynamic program and refined existence results for decentralized stochastic control[END_REF] "a general approach establishing that any sequential team optimization may admit a formulation appropriate for a dynamic programming analysis". One of the contributions of [START_REF] Yüksel | A universal dynamic program and refined existence results for decentralized stochastic control[END_REF] is to propose a construction of standard Borel controlled state and action spaces and to establish a universal dynamic program for stochastic control optimization problems -with information constraints, but without state -thus addressing some of the issues raised and left open by Witsenhausen. The ingredients are the following:

1. time t ∈ t 0 , T is discrete and runs among a finite set of consecutive integers; 5. η t : (Ω × s∈ t 0 ,t U s , F ⊗ s∈ t 0 ,t U s ) → (U t , U t ) t∈ t 0 ,T -1 are measurable mappings ("measurement constraints"); 6. P is a probability on (Ω, F);

7. j : (Ω × t∈ t 0 ,T -1 U t , F ⊗ t∈ t 0 ,T -1 U t ) → R + is a measurable function (criterion).
With these ingredients, Yüksel formulates a stochastic team optimization problem whose solutions (policies) are to be searched among sequences of measurable mappings ("design constraints") Y t-1 → U t , and their "randomized" versions (so-called strategic measures). He establishes a dynamic programming equation, where the Bellman functions are function of probability distributions and where the minimization is done over proper design mappings. One objective of Yüksel is to set up a mathematical framework under which the dynamic programming equation is mathematically sound [START_REF] Yüksel | A universal dynamic program and refined existence results for decentralized stochastic control[END_REF]Theorem 3.6].

Our approach The ingredients that we use are the following:

1. time t ∈ t 0 , T is discrete and runs among a finite set of consecutive integers;

2. (U t 0 , U t 0 ),. . . , (U T -1 , U T -1 ) are measurable spaces (control spaces);

3. (W t 0 , W t 0 ),. . . , (W T , W T ) are measurable spaces (noise);

4. ρ t:t+1 : W t 0 × t-1 s=t 0 (U s × W s+1 ) → ∆(W t+1 ), for t ∈ t 0 , T -1 , are stochastic kernels (noise distributions); The framework developed in this paper is intermediate between the ones of Evstigneev in [START_REF] Evstigneev | Measurable selection and dynamic programming[END_REF] and of Yüksel in [START_REF] Yüksel | A universal dynamic program and refined existence results for decentralized stochastic control[END_REF] -notable by the absence of a state space -and the ones of Witsenhausen [START_REF] Witsenhausen | A standard form for sequential stochastic control[END_REF], Hernández-Lerma and Lasserre [START_REF] Hernández | Discrete-Time Markov Control Processes: Basic Optimality Criteria[END_REF], Bertsekas and Shreve [START_REF] Bertsekas | Stochastic Optimal Control: The Discrete-Time Case[END_REF] and Puterman [START_REF] Puterman | Markov Decision Processes[END_REF] -where the state spaces are given for all times. This said, our preoccupation could be adapted to any of the above frameworks. Indeed, our objective is to establish a dynamic programming equation with a state, not at any time t ∈ t 0 , T , but at some specified instants t 0 < t 1 < • • • < t N = T . The state spaces are introduced as image sets (codomains) of what we call (time block) history reduction mappings (where history at time t consists of all uncertainties and controls prior to time t).

5. j : (W t 0 × T -1 s=t 0 (U s × W s+1 ), W t 0 ⊗ T -1 s=t 0 (U s ⊗ W s+1 )) → R is a measur- able function (criterion); 6. t 0 < • • • < t N = T

Stochastic dynamic programming with history feedbacks

To prepare the main result in Sect. 9.3, we establish a dynamic programming equation when the state is the history, that is, the uncertainties and the controls prior to the current stage (see the "canonical construction" in [17, p. 15]). Although quite natural, this equation is generally not written in the literature, as most frameworks in dynamic programming assume the a priori existence of a state (see §9.2.1).

From now on, time is discrete and runs among the integers t ∈ 0, T , where T ∈ N * is a positive integer (and where, for the sake of simplicity, we have taken t 0 = 0 regarding the notation in §9.2.1). We first define the basic and the composite spaces that we need to formulate multistage stochastic optimization problems. Then, we introduce a class of solutions called history feedbacks.

Histories and history spaces For each time t ∈ 0, T -1 , the control u t takes its values in a measurable set U t equipped with a σ-field U t . For each time t ∈ 0, T , the uncertainty w t takes its values in a measurable set W t equipped with a σ-field W t . For t ∈ 0, T , we define the history space H t equipped with the history field H t

H t = W 0 × t s=1 (U s-1 × W s ) , H t = W 0 ⊗ t s=1 (U s-1 ⊗ W s ) , ∀t ∈ 0, T ,
with the particular case H 0 = W 0 , H 0 = W 0 . A generic element h t = (w 0 , (u s-1 , w s ) s=1,...,t ) = (w 0 , u 0 , w 1 , u 1 , w 2 , . . . , u t-2 , w t-1 , u t-1 , w t ) ∈ H t is called a history at time t. For 1 ≤ r ≤ s ≤ t, we introduce the (r : s)-history subpart h r:s = (u r-1 , w r , . . . , u s-1 , w s ) ∈ H r:s = s τ =r (U τ -1 × W τ ), so that we have h t = (h r-1 , h r:t ).

History feedbacks For 0 ≤ r ≤ t ≤ T -1, we define a (r : t)-history feedback as a sequence {γ s } s=r,...,t of measurable mappings γ s : (H s , H s ) → (U s , U s ). We call Γ r:t the set of (r : t)-history feedbacks. The history feedbacks reflect the following information structure. At the end of the time interval [t -1, t[, an uncertainty variable w t is produced. Then, at the beginning of the time interval [t, t + 1[, a decision-maker chooses a control u t contingent on no more than the past, giving the chronology

w 0 ⇝ u 0 ⇝ w 1 ⇝ u 1 ⇝ • • • ⇝ w T -1 ⇝ u T -1 ⇝ w T .
Family of optimization problems with stochastic kernels We introduce a family of optimization problems with stochastic kernels. Then, we show how such problems can be solved by stochastic dynamic programming. In what follows, we say that a function is numerical if it takes its values in R = [-∞, +∞] (also called extended or extended real-valued function). To build a family of optimization problems over the time span 0, T -1 , we require two ingredients: a family {ρ s-1:s } s∈ 1,T of stochastic kernels

ρ s-1:s : (H s-1 , H s-1 ) → ∆(W s ) , ∀s ∈ 1, T , (9.1)
that represents the distribution of the next uncertainty w s parameterized by past history h s-1 , a numerical function, playing the role of a cost to be minimized,

j : (H T , H T ) → [0, +∞] , (9.2)
assumed to be nonnegative1 and measurable with respect to the field H T .

We define, for any feedback {γ s } s=t,...,T-1 ∈ Γ t:T-1 , a new family of stochastic kernels ρ γ t:T : (H t , H t ) → ∆(H T ), that capture the transitions between histories when the dynamics h s+1 = h s , u s , w s+1 is driven by u s = γ s (h s ) for all s in t, T -1 (see Definition 10 in Appendix A for the detailed construction of ρ γ r:t ; note that ρ γ t:T generates a probability distribution on the space H T of histories over the whole timespan 0, T ). We consider the following family of optimization problems, indexed by t in 0, T -1 and parameterized by the history h t ∈ H t : for all t in 0, T -1 , we define the minimum value

V t (h t ) = inf γ t:T -1 ∈Γ t:T -1 H T j(h ′ T )ρ γ t:T ( dh ′ T | h t ) , ∀h t ∈ H t , (9.3a)
and we also define

V T (h T ) = j(h T ) , ∀h T ∈ H T . (9.3b)
The numerical function V t : H t → [0, +∞] is called the value function at time t.

In the next paragraph, we show how the family {V t } t∈ 0,T of value functions can be used to solve, via dynamic programming, the optimization problem of interest whose value is

V 0 (w 0 ) = inf γ 0:T -1 ∈Γ 0:T -1 H T j(h ′ T )ρ γ 0:T ( dh ′ T | w 0 ) = inf γ 0:T -1 ∈Γ 0:T -1 W 1:T j Φ γ 0:T (w 0:T ) T s=1
ρ s-1:s dw s Φ γ 0:s-1 (w 0:s-1 ) , (9.4) by (A.5), where the flows Φ γ 0:s for s ∈ 0, T -1 are defined by Equation (A.3b) in Appendix A.

Bellman operators and dynamic programming We show that the value functions in (9.3)

V T = j , V t = B t+1:t V t+1 , for t = T -1, . . . , 1, 0 . (9.6)
This theorem is mainly inspired by [START_REF] Bertsekas | Stochastic Optimal Control: The Discrete-Time Case[END_REF]Chap. 8], with the feature that the state x t is, in our case, the canonical history h t , with the canonical dynamics h t+1 = h t , u t , w t+1 . This very general dynamic programming result will be the basis of all future developments in this paper. In the sequel, we assume that all the assumptions of Theorem 1 are fulfilled; all the spaces (like the ones introduced in §9.2.2) are Borel spaces; all the stochastic kernels (like the ones introduced in (9.1)) are Borel-measurable; all the criteria (like the one introduced in (9.2)) are nonnegative lower semianalytic functions. This Sect. 9.2 is mostly made of recalls and of statements that are straightforward consequences of results already established in the literature. However, the developements in §9.2.2 are indispensable to tackle time blocks decomposition in the coming Sect. 9.3.

State reduction by time blocks and dynamic programming

In this section, we consider the question of reducing the history using a compressed "state" variable. Differing with traditional practice, such a variable may not be available at any time t ∈ 0, T , but at some specified stages 0

= t 0 < • • • < t N = T .
We have seen in §9.2.2 that the history h t is itself a state variable with associated canonical dynamics h t+1 = h t , u t , w t+1 . However the size of this canonical state increases with t, which is an unpleasant feature for dynamic programming, hence the practical need to introduce a (ideally low dimensional) state space, at least at some specified stages, as done in this paper. As said in the introduction, the main difficulty is notational.

State reduction on a single time block

We first present the case where the reduction only occurs at two instants denoted by r and t, and such that 0 ≤ r < t ≤ T .

Definition 2. Let (X r , X r ) and (X t , X t ) be two measurable state spaces, θ r and θ t be two measurable reduction mappings

θ r : H r → X r , θ t : H t → X t , (9.7a)
and f r:t be a measurable dynamics

f r:t : X r × H r+1:t → X t . (9.7b)
The triplet (θ r , θ t , f r:t ) is called a state reduction across (r : t) if we have2 θ t (h r , h r+1:t ) = f r:t θ r (h r ), h r+1:t , ∀h t ∈ H t .

(9.7c)

The state reduction (θ r , θ t , f r:t ) is said to be compatible with the family {ρ s-1:s } r+1≤s≤t of stochastic kernels (9.1) if there exists a reduced stochastic kernel ρ r:r+1 : X r → ∆(W r+1 ), such that the stochastic kernel ρ r:r+1 in (9.1) can be factored as ρ r:r+1 ( dw r+1 | h r ) = ρ r:r+1 dw r+1 θ r (h r ) , for all h r ∈ H r , for all s in r + 2, t , there exists a reduced stochastic kernel ρ s-1:s : X r × H r+1:s-1 → ∆(W s ), such that the stochastic kernel ρ s-1:s can be factored as

ρ s-1:s ( dw s | (h r , h r+1:s-1 )) = ρ s-1:s dw s θ r (h r ), h r+1:s-1 , ∀h s-1 ∈ H s-1 .
According to this definition, the triplet (θ r , θ t , f r:t ) is a state reduction across (r : t) if and only if the diagram in the left part of Figure 9.1 is commutative; it is compatible if and only if the diagram in the center of Figure 9.1 is commutative.

H r × H r+1:t H t X r × H r+1:t X t θ r I d I d θ t f r:t H r × H r+1:s-1 ∆(W s ) X r × H r+1:s-1 θ r I d ρ s-1:s ρ s-1:s L 0 + (H t , H t ) L 0 + (H r , H r ) L 0 + (X t , X t ) L 0 + (X r , X r ) B t:
B t:r = B r+1:r • • • • • B t:t-1 , (9.9)
where the one time step operators B s:s-1 , for s in r + 1, t are defined in (9.5).

The following proposition is the key ingredient to formulate dynamic programming equations with a reduced state.

Proposition 3. Suppose that all the assumptions of Theorem 1 are satisfied. Suppose that there exists a state reduction (θ r , θ t , f r:t ) that is compatible with the family {ρ s-1:s } r+1≤s≤t of stochastic kernels (9.1) (see Definition 2). Then, there exists a reduced Bellman operator across (t : r) B t:r :

L 0 + (X t , X t ) → L 0 + (X r , X r ), such that B t:r φ t • θ r = B t:r ( φ t • θ t ) , ∀ φ t ∈ L 0 + (X t , X t ) . ( 9

.10)

For any φ t ∈ L 0 + (X t , X t ) and for any x r ∈ X r , we have that There is a practical case where state reductions can readily be obtained.

B t:r φ t (x r ) = inf ur∈Ur W r+1 ρ r:r+1 ( dw r+1 | x r ) inf u r+1 ∈U r+1 W r+2 ρ r+1:r+2 ( dw r+2 | x r , u r , w r+1 ) • • • inf u t-1 ∈U t-1 Wt ρ t-1:t ( dw t | x r , u r , w r+1 , . . . , u t-2 , w t-1 ) φ t f r:t (x r , u r , w r+1 , . . . , u t-1 , w t ) . ( 9
Remark 5 (Composed state dynamics as a straightforward reduction mapping).

We consider here the special case were the model is given by controlled state dynamics driven by noises. That is, we are given a family of measurable state spaces {(X s , X s )} s∈ 0,T and a family {f s:s+1 } s∈ 0,T -1 of measurable dynamics f s:s+1 : X s × U s × W s+1 → X s+1 . (9.12)

For any time s ∈ 0, T -1 , we define the composition f 0:s+1 = f s:s+1 •f s-1:s •. . .•f 0:1 with the abuse of notation that the composition is performed on the state argument.

Setting W 0 = X 0 , we obtain that f 0:s+1 : H s+1 → X s+1 is a mapping from the history space H s+1 taking values in the state space X s+1 . Now, given an integer N > 0 and an increasing sequence 0 = t 0 < • • • < t N = T of times, we define the family {θ t i } i∈ 0,N of measurable reduction mappings by θ t i = f 0:t i : H t i → X t i for i > 0, and by θ 0 = I d (the identity mapping on W 0 ) for i = 0. Moreover, given i and j ∈ 0, N , with i < j we obtain that

θ t j (h t j ) = θ t j (h t i , h t i +1:t j ) = f t i :t j θ t i (h t i ), h t i +1:t j , ∀h t j ∈ H t j , (9.13
)

with f t i :t j = f t j -1:t j • f t j -2:t j -1 • . . . • f t i :t i +1
which gives the state reduction Equation (9.7c).

There is a practical case where compatible state reductions can readily be obtained.

Theorem 7 remains valid with the reduced Bellman value functions given by

V t N = ℓ t N and V t i = B t i+1 :t i V t i+1 , ∀i ∈ 0, N -1 ,
and the reduced Bellman operator across (t i : t i+1 ) given, for any i ∈ 0, N -1 , for any φ t i+1 ∈ L 0 + (X t i+1 , X t i+1 ) and for any x t i ∈ X t i , by

B ti+1:ti φ ti+1 (x ti ) = inf ut i ∈Ut i Wt i +1 ρ ti:ti+1 ( dw ti+1 | x ti ) inf ut i +1∈Ut i +1 Wt i +2 ρ ti+1:ti+2 ( dw ti+2 | x ti , u ti , w ti+1 ) • • • inf ut i+1 -1∈Ut i+1 -1 Wt i+1 ρ ti+1-1:ti+1 ( dw ti+1 | x ti , u ti , w ti+1 , . . . , u ti+1-2 , w ti+1-1 )
ℓ ti (x ti , u ti , w ti+1 , . . . , u ti+1-1 , w ti+1 ) + φ ti+1 f ti:ti+1 (x ti , u ti , w ti+1 , . . . , u ti+1-1 , w ti+1 ) .( 9.17)

Of course, solving Equation (9.15) or Equation (9.17) can be as difficult as solving the original Bellman equation. However, the interest of such time block decomposition will be illustrated on the two time scale optimization problems, object of the next Sect. 9.4, as detailed at the end of §9.4.3.

Two time scale optimization problems

Some decisions problems naturally involve two different time scales, because of the timing of decisions -as for example long term investment decision and short term monitoring of physical devices. In this section, we introduce abstract mathematical notations to describe multistage decision problems with two time scales. Then, we show how they can be reformulated on a unique product timeline in order to obtain a block decomposition by Theorem 7.

In §9.4.1 and §9.4.2 we detail the structure and we formulate the two time scale optimization problems that we consider. In §9.4.3, we show how to decompose such problems by time blocks. In §9.4.4, we make the link with the classical framework of stochastic optimal control, and we illustrate the approach on a crude oil procurement problem in §9.4.5.

Structure of a two time scale optimization problem

We provide the data for a two time scale optimization problem.

Two time scales. We consider a multistage decision problem, with two time scales. The slow time scale is represented by a finite totally ordered set (S, ⪯) as follows -where s + denotes the successor of s ∈ S and s -its predecessor, and where we use the notation t ≺ t ′ for t ⪯ t ′ and t

̸ = t ′ - min S = s ≺ • • • ≺ s -≺ s ≺ s + ≺ • • • ≺ s = max S , (9.18a)
and the fast time scale by a finite totally ordered set (F, ⪯):

min F = f ≺ • • • ≺ f -≺ f ≺ f + ≺ • • • ≺ f = max F . (9.18b)
In a sense to be made more rigorous later (once a unified timeline will have been defined), each slow time interval [s, s + [ is made up of |F| (cardinality of F) fast time steps, hence the denomination "two time scale". For instance, S = {M o, T u, W e, T h, F r, Sa, Su} may represent days, whereas F = 1, 24 may represent hours within a day. In some problems, we might even take F = 0, 24 to handle the fact that two decisions (one slow and one fast) are taken at midnight, hence an additional fast time step 0.

Unified timeline. We define the unified timeline of the decision problem in two steps. First, we equip the product set S × F with the following lexicographic order:

(s, f) ≺ • • • ≺ (s -, f) ≺ (s, f) ≺ (s, f + ) ≺ • • • (9.19) • • • ≺ (s, f -) ≺ (s, f) ≺ (s + , f) ≺ • • • ≺ (s, f) .
More formally, we denote by (s, f) + the successor of (s, f) in S × F \ {(s, f)}, with

(s, f) + = (s, f + ) if f ̸ = f , (s + , f) if f = f . (9.20a)
Similarly, we denote by (s, f) -the predecessor of (s

, f) in S × F \ {(s, f)}, with (s, f) -= (s, f -) if f ̸ = f , (s -, f) if f = f . (9.20b)
As the slow time scale and the product time scale both represent physical times, we adopt the convention that the slow time s ∈ S is identified with the two scale time (s, f), as illustrated in Figure 9.2. For instance Monday is identified with (M o, 24).

In the product space S×F, the first time (s, f) does not coincide with a slow time ((M o, 0) does not correspond to Monday in our running example). Thus, we add to the product S×F an extra time denoted by (s -, f), corresponding to the extra slow time s -, which is such that (s, f) -= (s -, f). We denote by S the set {s -} ∪ S and by S×F the set (s -, f) ∪ (S×F), also called the extended timeline when equipped with an order ⪯ as follows

(s -, f) ≺ (s, f) ≺ • • • ≺ (s -, f) ≺ (s, f) ≺ (s, f + ) ≺ • • • • • • ≺ (s, f -) ≺ (s, f) ≺ (s + , f) ≺ • • • ≺ (s, f) . (9.21)
The two time scale optimization problem will be formulated on the extended timeline S×F, which we trivially identify with the time set 0, T , where T = |S| × |F|. of fast time scale dynamics measurable mappings, that represent the evolution "driven at the fast time scale" given, for all s ∈ S and f ∈ F \ {f}, by

s - s s + s- s (s -, f ) (s, f ) (s, f ) (s + , f ) (s + , f ) (s -, f ) (s, f ) (s, f ) S • • • • • • {s}×F S×F • • • {s + }×F • • • • • • {s}×F 1 Figure
F sf (s,f) : X sf (s,f) ×U sf (s,f) ×W sf (s,f) + → X sf (s,f) + , x sf (s,f) , u sf (s,f) , w sf (s,f) + → x sf (s,f) + = F sf (s,f) x sf (s,f) , u sf (s,f) , w sf (s,f) + , (9.22b)
where, for the sake of simplicity, we use the notation X sf (s,f) = X s s for all s ∈ S.

Criterion. We suppose given a family {Λ s } s∈S\{s} of slow time scale dynamics measurable instantaneous cost functions, with

Λ s -: X s s -× U s s -× W s s × f∈F\{f} X sf (s,f) × U sf (s,f) × W sf (s,f) + interval [s -,s[ → R , (9.23a)
for s ∈ S, and we suppose given a function Λ s representing a final cost, with

Λ s : X s s → R , (9.23b
ρ sf (s,f):(s,f) + : W s s × f f ′ =f + W sf (s,f ′ ) interval [s -,s[ -→ ∆(W sf (s,f) + ) , ∀s ∈ S , ∀f ∈ F\{f} , (9.25b)
with the convention that the Cartesian products of spaces in Equations (9.25a) and (9.25b) reduce to the empty set when the upper index of the Cartesian product is strictly lower that the corresponding lower index.

Formulation of a two time scale optimization problem on the product timeline

To apply Theorem 7, we introduce sets associated with the extended timeline (9.21) by

X (s,f) = X s s if f = f X sf (s,f) if f ̸ = f , ∀(s, f) ∈ S×F , (9.26a)
U (s,f) = U s s if f = f U sf (s,f) if f ̸ = f , ∀(s, f) ∈ S×F \ {(s, f)} , (9.26b)
W (s,f) = W s s if f = f W sf (s,f) if f ̸ = f , ∀(s, f) ∈ S×F , (9.26c)
W (s -,f) = X (s -,f) (9.26d)
and a family of state dynamics From these sets, we deduce the history sets and the histories

F (s,f) : X (s,f) ×U (s,f) ×W (s,f) + → X (s,f) + defined by F (s,f) = F s s if f = f F sf (s,f) if f ̸ = f , ∀(s, f) ∈ S×F \ {(s, f)} . (9.27) s s + (s, f ) (s + , f ) (s + , f + ) (s + , f -) (s + , f )   X s s (= X sf (s, f ) ) ×U s s ×W s s +      X sf (s + ,f ) ×U sf (s + ,f ) ×W sf (s + ,f ) +       X sf (s + ,f + ) ×U sf (s,f + ) ×W sf (s + ,f + ) +       X sf (s + , f -) ×U sf (s + , f -) ×W sf (s + , f )       X sf (s + , f ) (= X s s + ) ×U s s + ×W s (s + ) +       X (s, f ) ×U (s, f ) ×W (s, f ) +       X (s + ,f ) ×U (s + ,f ) ×W (s + ,f ) +       X (s + ,f + ) ×U (s,f + ) ×W (s + ,f + ) +      X(s + , f -) ×U (s + , f -) ×W (s + , f )      X (s + , f ) ×U (s + , f ) ×W (s + , f ) +    • • • F s s F sf (s + ,f ) • • • F sf (s + , f -) F (s, f ) F (s + ,f ) • • • F (s + , f -) 1
H (s,f) = W (s -,f) × (s,f)≺(s ′ ,f ′ )≺(s,f) U (s ′ ,f ′ ) -× W (s ′ ,f ′ ) , ∀(s, f) ∈ S×F , (9.28a) h (s,f) = w (s -,f) , u (s ′ ,f ′ ) -, w (s ′ ,f ′ ) (s,f)≺(s ′ ,f ′ )≺(s,f) , ∀(s, f) ∈ S×F , (9.28b)
and, for suitable indices, the partial history sets and the partial histories

H (s,f):(s ′ ,f ′ ) = (s,f)≺(s ′′ ,f ′′ )≺(s ′ ,f ′ ) (U (s ′′ ,f ′′ ) -× W (s ′′ ,f ′′ ) ) , (9.29a)
h (s,f):(s ′ ,f ′ ) = (u (s ′′ ,f ′′ ) -, w (s ′′ ,f ′′ ) ) (s,f)≺(s ′′ ,f ′′ )≺(s ′ ,f ′ ) . (9.29b)
The criterion formulated in Equation (9.24) combined with state dynamics leads to a criterion j : H (s,f) → R.

Based on the stochastic kernels (9.25b) and (9.25a), we introduce stochastic kernels ρ (s,f):(s,f) + associated with the extended timeline (9.21), for each (s, f) ∈ S×F \ {s, f}, by Note that, for f ̸ = f, the kernels ρ (s,f):(s,f) + : H (s,f):(s,f) → ∆(W (s,f) + ), only depend on the partial history uncertainty part from (s, f) to (s, f).

ρ (s,f):(s,f) + : H (s,f) -→ ∆(W (s,f) + ) h (s,
The components of the problem are now formulated on the extended timeline S×F, already identified with the time set 0, T . Thus, we are in the framework of §9.2.2 and we aim at solving an optimization problem as formulated in Equation (9.4).

Two time scale decomposition

The existence of Bellman equations for a two time scale optimization problem is given by the following proposition. Proposition 9. Consider a two time scale optimization problem as formulated in §9.4.1 and §9.4.2. The optimization problem (9.4) has a solution given by a dynamic programming equation at the slow scale. More precisely, let (V s ) s∈S be given by V s = Λ s and, for s ∈ S \ {s}, by the backward induction • • • • • F sf (s + ,f) • F s s associated with the state dynamics defined in Equations (9.22). Then, the value of the optimization problem (9.4) is given by V s -(x s s -).

V
Proof. The proof is an application of Theorem 7 with the help of Remarks 5 and 6. First, we have re-framed in §9.4.2 the two time scale optimization problems described in §9.4.1 in the formalism of §9.2.2 with the help of the extended timeline (9.21). Second, as we are given state dynamics (9.27) on the extended timeline and thanks to Remark 5, we obtain a state reduction at times {(s, f)} s∈S by composition of the state dynamics. Moreover, as the slow time scale kernels given by Equation (9.25a) are constant, the state reduction across the slow time scale is compatible with the stochastic kernels (see Remark 6). Third, the case of a time additive criterion has been considered in Corollary 8. We are thus able to apply Theorem 7 and obtain the slow time scale Bellman recursion (9.31) as a special case of Equation (9.17).

The slow time scale Bellman equation (9.31) is as difficult to solve as the Bellman equation on the extended timeline. However, the interest of (9.31) lies elsewhere. Imagine that one is able to obtain, in a relatively easy way, lower V s and upper V s approximations of V s in (9.31). Then, by replacing the last term V s + of (9.31) by either V s + or V s + , one can now solve a (lower or upper) surrogate of Equation (9.31) by any suitable method. For instance, one could use scenario decomposition methods, like progressive hedging [START_REF] Rockafellar | Scenarios and policy aggregation in optimization under uncertainty[END_REF], that do not require statistical independence of noises within the slow time interval [s, s + [. Thus, the two time scale optimization problem as formulated in §9.4.1 and §9.4.2 can be approximatively solved, from below and from above, by a mix of slow time scale dynamic programming and of (for example) progressive hedging (or any other method, including dynamic programming).

This approach was followed in the initial implementation of the time blocks decomposition [START_REF] Rigaut | Time Decomposition Methods For Optimal Management Of Energy Storage Under Stochasticity[END_REF]. There, time blocks decomposition was used to produce algorithms tackling a two time scales battery management problem over 20 years. This problem involved both the battery operation (with a fast time step of 30 minutes) and the battery replacement (with a slow time step of one day). Despite involving several hundred thousand time steps, the problem was solved using a reasonable CPU time. Our contribution is a clarification of the time blocks framework initially introduced in [START_REF] Rigaut | Time Decomposition Methods For Optimal Management Of Energy Storage Under Stochasticity[END_REF]. Additionally, we put a greater emphasis on developing the time blocks decomposition for the two time scales problems.

Link with the classical framework of stochastic optimal control

The property that the stochastic kernels (9. The integral cost given in the right hand side of Equation (9.33a) can be reformulated as an expectation, denoted by E, with respect to the probability ρ (s,f):(s,f) by introducing random variables for the exogeneous noises as projection mappings from W (s,f):(s,f) to W (s,f) for all (s, f) ∈ S×F W (s,f) : W (s,f):(s,f) → W (s,f) , ∀(s, f) ∈ S×F , (9.34) and obtaining random variables for the states and the control through the dynamics equations (9.33b)-(9.33c) and the feedback equations (9.33d)-(

where the two feedback constraints in Equations (9.33d) and (9.33e) are reformulated as measurability constraints (9.35e) and (9.35g) (of course, a formal equivalence would require to be more specific about spaces to use Doob functional Lemma).

Illustration with the crude oil procurement problem

Crude oil procurement is the part of the oil supply chain that sits between the production of crude oil and its processing in a refinery. The goal of procurement is to purchase crude oil from various suppliers around the world and having it delivered in time to the refinery to be processed. As illustrated in Figure 9.4, every month (on the bottom line) a refinery receives crudes that have been bought during the 8 previous weeks (on the upper line). The problem naturally displays two time scales. On the one hand, deliveries to the refinery are made at the beginning of each month, and crude consumption is set once a month. On the other hand, crude oil shipments can be purchased at the frequency of the week; every week, a selection of shipments is presented to Notations Crude oil procurement from §9. Now that all the elements from §9.4.1 have been identified, Proposition 9 enables us to write a dynamic programming equation such as (9.31) at the scale of the month, without losing the time-dependency of crude prices inside the month. This illustration stems from a research work done in partnership with TotalEnergies, in the context of a PhD thesis [START_REF] Martin | Stochastic Optimization for the Procurement of Crude Oil in Refineries[END_REF].

Conclusion and perspectives

As said in the introduction, decomposition methods are appealing to tackle multistage stochastic optimization problems, as they are naturally large scale. The most common approaches are time decomposition (and state-based resolution methods, like stochastic dynamic programming, in stochastic optimal control), and scenario decomposition (like progressive hedging in stochastic programming).

This paper is part of a general research program that consists in mixing different decomposition bricks. Space decomposition methods have been investigated in [3] and [8]. Here, we have tackled the issue of using time blocks decomposition in such a way that stochastic dynamic programming is used at the slow time scale with an appropriate white noise assumption, whereas stochastic programming methods such as progressive hedging can be used at the fast time scale where such an independence assumption does not hold. This approach paves the way of mixing time decomposition with scenario decomposition. For this purpose, we have revisited the notion of state, and have provided a way to perform time decomposition but only accross specified time blocks.

Chapter 10 Conclusion

The procurement of crude oil is the part of the oil supply chain that sits between the production of crude oil and the operation of refineries. The goal of procurement is to supply a refinery with crude oil in order to ensure its operation. On the one hand, refineries work at a monthly scale; crude oil shipments are delivered to the refinery at the beginning of every month; then, the decision maker sets a consumption for the upcoming month. On the other hand, purchases are made at the weekly scale; different shipments are presented during the eight weeks preceding each focus month; then, the decision maker sets orders. Therefore, as illustrated in Figure 10.1, there is a delay between the moment an order is passed and the moment the corresponding shipment is delivered to the refinery. This creates an intricate decision process and, on top of that, there are uncertainties regarding economic variables. The goal of this thesis was to formalize multistage stochastic optimization problems and to propose resolution methods.

Part II is the most abstract part of the thesis as we provided a mathematical representation of procurement problems with any number of months. We developed a framework that takes advantage of the month/week structure of the problem to write a dynamic programming equation at the scale of the month, without requiring independence of uncertainties between weeks inside a month.

Part I tackles the case of crude oil procurement in which the refinery operates for one month. We introduced a model for procurement that we used to formulate optimization problems and, ultimately, to build policies. The five resulting policies were compared to the method currently used by TotalEnergies in two tests, a Monte-Carlo simulation and replays of historical scenarios.

While SDP-based policies dominated the Monte-Carlo simulation, the results were not as clear-cut on replays of historical scenarios. We now discuss this discrepancy. Each week, predictions are given to the decision maker by a trading team • denotes purchase controls and □ denotes consumption decisions in TotalEnergies. For computational reasons, traditional SDP policies did not account for these predictions and ended up being out-performed by single-scenario based policies. Subsequently, the policy mixing stochastic dynamic programming and the predictions was the best performing one. Ultimately, the numerical results that we have obtained highlight the potential gains that stochastic optimization methods could bring to the procurement of crude oil. They also point at two directions where improvements could be made and at one intrinsic limitation. First, the discrepancy between the results on the Monte-Carlo simulation and the results on the historical scenarios suggests that one should pay attention to dispose of more representative scenarios, particularly concerning time dependency of economic variables. Second, given the results on the historical scenarios, incorporating the price predictions in a policy seems necessary. Third, TotalEnergies's tool to optimize and simulate the operations of a refinery had to be foregone in favor of a gross approximation, due to computational load. Indeed, it is too complex, and too slow, to be used in the context of multistage stochastic optimization.

List of Figures

Figure 1 . 1 : 2 Figure 1 . 2 :

 11212 Figure 1.1: Photograph of the Zoroaster [25], first tanker. length: 54 m, capacity: 240 tons

Figure 1 . 3 :Figure 1 . 4 :

 1314 Figure 1.3: Repartition of oil wells in the world

Figure 1 . 6 :

 16 Figure 1.6: Illustration of elements to take into account when purchasing crude oil

Figure 2 . 1 :

 21 Figure 2.1: Photograhie du Zoroaster [25], premier pétrolier. longueur: 54 m, capacité: 240 tonnes

Figure 2 . 2 :

 22 Figure 2.2: Photographie du AbQaiq, un petrolier moderne. longueur: 333 m, capacité: ∼ 250.000 tonnes Le pétrole, à fortiori brut, a été au centre du développement économique du XXe siècle et est progressivement devenu omniprésent dans notre société. Toutefois, ce n'est pas une ressource naturelle qui est facile à exploiter. Comme l'illustre Figure 2.3, c'est une ressource à laquelle il est difficile d'accéder. En outre, comme présentée dans Figure 2.4, c'est aussi une ressource dont les lieux de production et consommation sont relativement éloignés. En effet, les plus grands consommateurs sont l'Union européenne, les États-Unis et la Chine, mais ceux-ci n'en produisent que très peu. Enfin, c'est une ressource qui est aussi difficile à utiliser, obtenir des produits utilisables requiert un complexe et coûteux traitement. La chaîne d'approvisionnement du pétrole brut est généralement subdivisée entre chaînes amont et avale. La chaîne en amont comprend tout ce qui se passe

Figure 2 . 4 :

 24 Figure 2.4: Flux de pétrole brut dans le monde selon OPEC 2016 Annual Statistical Bulletin

Figure 3 . 1 :

 31 Figure 3.1: General representation of the procurement for a single month.

Figure 3 . 2 :Figure 3 . 3 :

 3233 Figure 3.2: Example of repartition of crude oils given their density and sulfur content

Figure 3 . 4 :

 34 Figure 3.4: Simplified view of a distillation column

Figure 3 . 5 :Figure 3 . 6 :Figure 3 . 7 :

 353637 Figure 3.5: Geographical position of the Donges refinery

Figure 3 . 8 :

 38 Figure 3.8: Example of monthly crude oil procurement. The decision taker must purchase crude oil during the months M 1 and M 2 to feed the refinery in the month M 3

C

  set of crudes on the market c ∈ C index for a crude in C ∆ c ∈ N delay from order to delivery for crude c ∆, ∆ max/min order delay (number of weeks) G ⊂ R + set of existing cargo sizes, in barrels (bbl) B c (m,w) ⊂ G set of available cargos for crude c in (m, w) b c (m,w) ∈ R + volume of crude c purchased in week (m, w) B (m,w) = C∈C B c (m,w) set of available cargos in week (m, w) b (m,w) ∈ B (m,w) crude oil volumes purchased in week (m, w)

Figure 3 . 11 :

 311 Figure 3.11: Timeline of purchase and delivery of crude c targeting the month m

8 Figure 3 . 12 : 2 3. 3 . 1 . 3

 83122313 Figure 3.12: Example of crude oil availability over months M 1 and M 2

Figure 3 . 13 :

 313 Figure 3.13: Schematic timeline of the different elements constituting the real cost of a crude oil c. The premium, in red, is the only source of uncertainty considered.

  with b = (b c ) c∈C , as in (3.8b) , (3.11d) w = (w c ) c∈C , as in (3.10) , (3.11e) the total cost of the purchase decision b t in week t.

Figure 4 . 1 :

 41 Figure 4.1: Scheme of the monthly procurement problem. Purchases are made each week through M 1 and M 2 and are delivered at the beginning of M 3 for a consumption during the month

  M 3

Figure 7 . 1 :

 71 Figure 7.1: Crudes availability timing for the problem treated in Chapter 7

Figure 7 . 2 :

 72 Figure 7.2: Extract of the history of crudes prices, ranging from 01/01/2010 to 01/01/2021

Figure 7 . 3 :

 73 Figure 7.3: Histogram of the daily reference quotations over a 10-years period (n=2778)

Figure 7 . 4 :

 74 Figure 7.4: Histogram of daily premiums for the crude B5 over a 10-years period (n=2778). In black, we draw the histogram of a Gamma distribution with parameters κ B5 = 3.19, θ B5 = 0.48

Figure 7 . 5 :

 75 Figure 7.5: Extract from the list of products prices vectors

Figure

  Figure 7.6: Histogram of operating margins over Monte-Carlo for five policies: Expert, Triplet, MPC, SDP esp and SDP CVaR .

Figure 7 . 7 :Table 7 . 3 :Figure 7 . 8 : 7 ]Figure 7 . 9 :

 777378779 Figure 7.7: Histogram of the difference between SDP esp and Expert across 1000 assessment scenarios.

Figure 7 . 10 :

 710 Figure 7.10: Left: Histogram of the score difference between SDP esp and Expert over the assessment set. Right: Difference between SDP esp and MPC, for the 1000 assessment scenarios, sorted

Figure 7 . 11 :

 711 Figure 7.11: Extract of the data used to compute w EKO (O,1)

Figure 7 .

 7 11, we show an extract of the source data used to build w B5 (O,1) by averaging the difference between BEKO and BBF O,

Figure 7 . 12 :

 712 Figure 7.12: Extract from the product prices of the last four weeks of 2020, with the resulting prices for December on the right

  .4b) the list of cargos purchased in week (m, w) for a delivery at the beginning of month m. notation space meaning B m ′ ,c (m,w) ⊂ V c × Q c set of shipment (volume, quality) of crude c available in week (m, w) for a delivery at the beginning of month m ′ b m ′ ,c (m,w) ∈ B m ′ ,c (m,w) cargo of crude c purchased at week (m, w) for a delivery at the beginning of month m ′ B m ′ (m,w) ⊂ c∈C (V c × Q c ) set of cargo combinations available in week (m, w) for a delivery at the beginning of month m ′ b m ′ (m,w) ∈ B m ′ (m,w) cargos purchased in week (m, w) for a delivery at the beginning of month m ′ B (m,w) = m ′ ∈(m,w)P B m ′ (m,w) set of cargo combinations available in week (m, w) regardless of the delivery month b (m,w) ∈ B (m,w) cargos purchased in week (m, w) regardless of the delivery month Table 8.4: Purchase notation Finally, we denote by b (m,w) = (b m ′ (m,w) ) m ′ ∈(m,w)P ∈ B (m,w) = m ′ ∈(m,w)P B m ′ (m,w) , (8.4c) the vector of purchase vectors in week (m, w) for all delivery months m ′ ∈ (m, w)P.

  for unit u for the month m R m = u∈U R u m set of settings for the whole refinery for the month m r m ∈ R m settings applied to the refinery for the month mTable 8.6: Settings notations

R

  selling price space of the product p during the month m P m R |P| +

  .10a) the market prime per volume unit of the product p in month m and by p m = (p p m ) p∈P ∈ P m =

  notation meaning Ω m ′ (m,w) (d, b, w) purchase cost concerning the m ′ -buffer in week (m, w) Ψ m (s, d, u s , r, p) production costs for the refinery during the month m Table 8.10: Cost functions notations The total cost for operating the refinery over the whole time span T = M × W is (m,w)∈M×W m ′ ∈(m,w)P Ω m ′ (m,w) (d m ′ (m,w) , b m ′ (m,w) , w (m,w) ) + m∈M Ψ m (s m , d m (m,w) , u s m , r m , p m ) .

  2. (Ω, F) is a measurable space (Nature); 3. (U t 0 , U t 0 ),. . . , (U T -1 , U T -1 ) are measurable spaces (control spaces); 4. (Y t 0 , Y t 0 ), . . . , (Y T -1 , Y T -1 ) are measurable spaces ("observation" spaces);

Figure 9 . 3 :

 93 Figure 9.3: Original dynamics and their reformulation on the product timeline on the slow time interval [s, s + [

4 . 1 S

 41 set of months during which we manage the refinery; in Figure 9.4, S = {M 1 , M 2 , M 3 } F set of weeks in each month; in Figure 9.4, F = {1, 2, 3, 4, 5} U s s set of crude oil consumptions during the month s + W s s + set of product prices for the month s + U sf (s,f) set of crude shipments purchased in week (s, f) W sf (s,f) + set of crude oil prices in week (s, f) F sf (s,f) accumulation of shipments purchased in (s, f) F s s delivery of orders and consumption of crude oil for the month s + Λ s operational costs during the month s (crude oil purchases during s -earnings from production) Λ M 4 end cost associated with the state x s M 3 = x sf (M 3 ,5)valuation of the buffers and stocks in the refinery before the beginning of the month M 4

Figure 10 . 1 :

 101 Figure 10.1: Example of crude oil procurement over 3 months.

1. 1

 1 Photograph of the Zoroaster [25], first tanker. length: 54 m, capacity: 240 tons . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1.2 Photograph of the AbQaiq, a modern-age tanker. length: 333 m, capacity: ∼ 250.000 tons . . . . . . . . . . . . . . . . . . . . . . . . 1.3 Repartition of oil wells in the world . . . . . . . . . . . . . . . . . . 1.4 Crude oil flows according to OPEC 2016 Annual Statistical Bulletin 1.5 Schematic representation of the processing steps inside a refinery . . 1.6 Illustration of elements to take into account when purchasing crude oil . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2.1 Photograhie du Zoroaster [25], premier pétrolier. longueur: 54 m, capacité: 240 tonnes . . . . . . . . . . . . . . . . . . . . . . . . . . 2.2 Photographie du AbQaiq, un petrolier moderne. longueur: 333 m, capacité: ∼ 250.000 tonnes . . . . . . . . . . . . . . . . . . . . . . . 2.3 Répartition des puits de pétrole dans le monde. . . . . . . . . . . . 2.4 Flux de pétrole brut dans le monde selon OPEC 2016 Annual Statistical Bulletin . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2.5 Représentation schématique des différentes étapes de raffinage . . . 2.6 Illustration des elements a prendre en compte lors de l'achat de petrole brut. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3.1 General representation of the procurement for a single month. . . . 3.2 Example of repartition of crude oils given their density and sulfur content . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3.3 Crude oil general composition . . . . . . . . . . . . . . . . . . . . . 3.4 Simplified view of a distillation column . . . . . . . . . . . . . . . . 3.5 Geographical position of the Donges refinery . . . . . . . . . . . . . 3.6 The oil fields appear in red, compared to the refinery in blue . . . . 3.7 Example of price variations over 3 months of the reference crude, the Brent . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3.8 Example of monthly crude oil procurement. The decision taker must purchase crude oil during the months M 1 and M 2 to feed the refinery in the month M 3 . . . . . . . . . . . . . . . . . . . . . . . . 3.9 Example of decision making in the week 5: Cabinda is no longer available, Azeri is available, and Ekofisk is not yet available (its price is not yet known) . . . . . . . . . . . . . . . . . . . . . . . . . 3.10 Time discretization scheme; everything that happens during week w is summed up in the point w which starts the week . . . . . . . . 3.11 Timeline of purchase and delivery of crude c targeting the month m 3.12 Example of crude oil availability over months M 1 and M 2 . . . . . . 3.13 Schematic timeline of the different elements constituting the real cost of a crude oil c. The premium, in red, is the only source of uncertainty considered. . . . . . . . . . . . . . . . . . . . . . . . . . 4.1 Scheme of the monthly procurement problem. Purchases are made each week through M 1 and M 2 and are delivered at the beginning of M 3 for a consumption during the month . . . . . . . . . . . . . . 4.2 Illustration of the hidden markov chain modeling the crude oil premiums . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7.1 Crudes availability timing for the problem treated in Chapter 7 . . 7.2 Extract of the history of crudes prices, ranging from 01/01/2010 to 01/01/2021 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7.3 Histogram of the daily reference quotations over a 10-years period (n=2778) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7.4 Histogram of daily premiums for the crude B5 over a 10-years period (n=2778). In black, we draw the histogram of a Gamma distribution with parameters κ B5 = 3.19, θ B5 = 0.48 . . . . . . . . . 7.5 Extract from the list of products prices vectors . . . . . . . . . . . . 7.6 Histogram of operating margins over Monte-Carlo for five policies: Expert, Triplet, MPC, SDP esp and SDP CVaR . . . . . . . . . . . . . 7.7 Histogram of the difference between SDP esp and Expert across 1000 assessment scenarios. . . . . . . . . . . . . . . . . . . . . . . . . . . 7.8 Zoom of Figure 7.7 on the interval [-1.10 7 , 1.10 7 ] . . . . . . . . . . 7.9 Histogram of the score difference between SDP esp and SDP CVaR over the assessment set . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7.10 Left: Histogram of the score difference between SDP esp and Expert over the assessment set. Right: Difference between SDP esp and MPC, for the 1000 assessment scenarios, sorted . . . . . . . . . . . 7.11 Extract of the data used to compute w EKO (O,1) . . . . . . . . . . . . . .

  physiques, comme un retard de livraison. En outre, l'acheteur ne connaît pas non plus exactement à l'avance quel sera l'état des stocks de la raffinerie à la livraison ; bien souvent, il se base sur son expérience et son intuition pour envisager quelques possibilités. Contrairement à la majorité des travaux s'intéressant à l'approvisionnement, notre contribution ne se focalise pas sur le pilotage de la raffinerie et préfère considérer celle-ci comme une boite-noire sur laquelle nous n'avons que peu d'influence, seulement la consommation. En revanche, nous nous concentrons sur l'impacte qu'on les délais de livraison dans le processus d'achat de brut au cours des semaines précédant une date de livraison. Plus spécifiquement, nous produisons des problèmes d'optimisation stochastique multiétapes dans lequel l'acheteur doit, à intervalles réguliers, sélectionner les bruts qu'il juge intéressants pour une livraison future.

	Demand and contracts	Products prices
	Oil prices	Pending orders
	Oil avail-	Refinery
	ability	schedule

Figure 2.6: Illustration des elements a prendre en compte lors de l'achat de petrole brut. aléas

  .9. Figure 3.9: Example of decision making in the week 5: Cabinda is no longer available, Azeri is available, and Ekofisk is not yet available (its price is not yet known)

	Not yet available
	(Price unknown)
	Ekofisk crude
	???$/bbl
	Available now
	(Price known)
	Azeri crude
	2.5$/bbl
	Too late
	Cabinda crude
	1.2$/bbl

Table 3 .

 3 .3. 3: Existing oil tankers categories and corresponding loads

	Size categories	tons deadweight (DWT) volume capacity (bbl)
	Handysize Panamax Aframax Suezmax Very Large Crude Carrier 200,000 -320,000 10,000 -60,000 60,000 -80,00 80,000 -120,000 120,000 -200,000 Ultra Large Crude Carrier 320,000 -550,000	75.10 3 -450.10 3 450.10 3 -600.10 3 600.10 3 -800.10 3 800.10 3 -1.5.10 6 1.5.10 6 -2.4.10 6 2.4.10 6 -4.10 6

  .1 and §6.3.2, we solve a deterministic dynamic optimization problem based on a projected scenario (w t , w t + , . . . , w t , s M 3 , p M 3 ) (6.9) where ( w t ′ ) t ′ ∈ t + ,t is built in accordance with the stochastic model detailed in §4.3.1. M 3 of p M 3 is given A projection s M 3 of s M 3 is given for i ∈ 1, 100 do Use Algorithm 12 to generate (w i t , w i t + , . . . , w i t ) end for Compute a mean projected scenario (w t , w t + , . . . , w t ) Solve the deterministic problem

	Algorithm 4 MPC purchase policy
	procedure ϕ mpc

t (d t , w t ) A projection p

  [START_REF] Adhya | A Lagrangian Approach to the Pooling Problem[END_REF], that describes all the crude oil combinations that can be received. Then, each set D t -∈ R |C| + is recursively deduced from D t and B t -, respectively the next viable state set and the set of possible purchases in week t -.Once the sequence of admissible state sets {D t } t∈T∪{t + } has been recursively computed, we propose a second Algorithm 6 to compute B t (d), the set of admissible controls generated by the mappings introduced in §5.2.3.In Algorithm 6, the viable control set B t (d) is built by checking every possible control b ∈ B t . For each b, if the dynamic sends d on an element of the next viable set D t + , then b is added to the viable control set.

	Algorithm 6 Computation of the viable control set
	procedure B t (d)
	B t = {∅} for b ∈ B t do for d ′ ∈ D t + do if d + b = d ′ then B t ← B t ∪ {b} break;	▷ verify if d + b ∈ D t + ▷ add b to the set of viable controls
	end if
	end for
	end for
	Return B
	end procedure

  Retain the minimum value across | B t (d)| values end for Compute the mean value across |W t | values end for Store the |D t | values computed for V t t ← t - end while Return {V t } t∈T end procedure

t while t ⪰ t do for d ∈ D t do for w ∈ W t do for b ∈ B t (d) do Compute Ω t (b, w) + V t + (d + b) end for

  d, p M 3 ) end for t = t while t ⪰ t do for d ∈ D t do for w ∈ W t do for b ∈ B t (d) do Compute Ω t (b, w) + V λ,β t + (d + b) end for Retain the minimum value across | B t (d)| values end for Compute the mean value across |W t | values Compute the CVaR end for Store the |D t | values computed for V λ,β

		t
	t ← t -end while
	Return {V λ,β t end procedure	} t∈T
	Algorithm 9 Step forward optimization
	procedure ϕ t (d t , w t )
	Solve
		b * t ∈ arg min

b∈ B t (d t )

  .2.3. We now present, in Algorithm 10, a method where we use the time available (48-72h) to compute another set of value functions each week. (d t , w t ) A projection p M 3 of p M 3 is given A projection s M 3 of s M 3 is given Build a new design set of scenarios for the remaining weeks [t, t] that uses w t , p M 3 and s M 3

	Algorithm 10
	procedure ϕ t

  1 , light 1 , balanced 2 , heavy 2 , light 2 , balanced 3 , heavy 3 , ligh 3 . Consequently, the purchase decisions b t ∈ R 57 + every week t, introduced in §3.3.1, have 57 components, and the buffer d t ∈ R 57 + , introduced in §5.2, as well.

Table 7 .

 7 7.6: Histogram of operating margins over Monte-Carlo for five policies: Expert, Triplet, MPC, SDP esp and SDP CVaR . 1: Average score of each policy computed with the Monte-Carlo simulationAnother observation is that Expert is the worst performing policy among all policies. Looking at the corresponding histogram, the difference does not seem to come from good scenarios, but rather from bad ones. As highlighted in Table7.2, Expert leads to disastrous results in numerous scenarios while this happens less often for other policies. The four other policies also appear to somewhat mitigate their losses when compared to Expert.

		Expert Triplet MPC SDP esp SDP CVaR
	average ( .10 7 $)	4.00	4.96	4.46	6.79	6.71
	gap (vs Expert)	0%	24%	12%	70%	68%
	interval	Expert Triplet MPC SDP esp SDP CVaR
	-5.10 7 ≤ • • • ≤ 0 -1.10 8 ≤ • • • ≤ -5.10 7 -1, 5.10 8 ≤ • • • ≤ -1.10 8	138 93 36	111 54 0	121 88 0	61 0 0	60 0 0

Table 7 .

 7

2: Distribution of scenarios incurring loses for each policy. Each interval corresponds to a x-axis grade in table 7.1.

Table 7 .

 7

4: Operational margin and combination of crude oils generated by each policy for the historical scenario of December 2020

Table 7 .

 7

	6: Operational margin and combination of crudes generated by each policy
	for the historical scenario of November 2020
	policy	Expert Triplet MPC SDP esp SDP CVaR Suc-SDP optimum
	1 st crude	L5	H2	L1	B5	B5	L1	L1
	2 nd crude	H5	B2	H1	B5	B5	H1	H1
	3 rd crude	B3	L4	B5	B5	B5	B5	B5
	margin (.10 7 $) gap (to Expert)	-5.15 -2.84 0 44.8% 179% 53.6% 4.07 -2.39	-2.39 53.6%	4.07 179%	4.07 179%
	Table 7.7: Operational margin and combination of crudes generated by each policy
	for the historical scenario of January 2021
	For the most part, the analysis formulated in §7.4.2 for the month of December
	2020 remains true for the other months from October 2020 to March 2021. In fact,

Table 7 .

 7 9: Operational margin and combination of crudes generated by each policy for the historical scenario of March 2021

  .2 the notations used for time description.

	notation		set	meaning
	M			set of months
	m W	∈	M	index for a month set of weeks in a month
	w M × W (m, w)	W ∈ M × W couple designating a week w in month M index for a week in a month ∈ product set of all weeks in months M
			Table 8.2: Indexing of stages types

Table 8 . 3

 83

	Pm (m, w)P ⊂ ⊂	M × W M	set of purchase weeks for a delivery in month m set of months with a purchase opportunity in the week (m, w)

.2c) 8.2.1.3 Purchase/delivery relations We summarize in Table 8.3 the notations used to link weeks of purchase to months of delivery. notation set meaning P ⊂ (M × W) × M relation between order weeks and months P ⊂ (M × W) × M relation for buffer existence : Week/month relations for orders and buffer existence

Table 8 . 7

 87

: Stocks variables

Buffers. The lifespan of the m ′ -buffer is limited. That is precisely the function of the relation P, introduced in 8.3d (m, w)Pm ′ ⇐⇒ the m ′ -buffer is active in week (m, w) .

(8.7a)

Table 8 .

 8 set of acceptable crude oil deliveries for the month m

11: Oil consumption notations

Availability of shipments. The limited availability of shipments was introduced in §8.2.1.4 and is the first constraint the decision maker is faced with. Given there are few different tanker sizes, the decision maker are limited to selecting one of the few cargos that are presented to him, hence leading to the constraint (8.4c).

Table 8 .

 8 .12, we present the notations used for controls and uncertainties in a SOC reformulation.

	notation	space	meaning
	O O u t w t	⊂ ⊂ ∈ see (8.22a) control variable applied at the beginning of step [t, t + [ binary relation between order indexes and deliveries T × T binary relation for buffer existence in T T × T ∈ see (8.23) uncertainty revealed at the beginning of step [t, t + [

12: SOC notations for controls and uncertainties

  2.2.1 is now defined at the scale of the scale W. To fit the monthly model, the stock s t only varies when stage t corresponds to a fictitious stage (m, w). (s t , {d t ′ t } t ′ ∈tO , u t , w t ) instantaneous cost associated with the stage t

	function	meaning
	Λ t Table 8.13: Notation for the instantaneous cost function
	8.3.1.3 Cost functions

  3. (U t 0 , U t 0 ),. . . , (U T -1 , U T -1 ) are measurable spaces (control spaces); 4. ν t:t+1 : X t × U t → ∆(X t+1 ) is a stochastic kernel, for t ∈ t 0 , T -1 (transitions); 5. L t : X t × U t → R, for t ∈ t 0 , T -1 , and K : X T → R, are measurable functions (instantaneous and final costs).With these ingredients, Puterman formulates a stochastic optimization problem with a time additive cost function over given state and control spaces, whose solutions are to be searched among history feedbacks, namely sequences of mappingsX t 0 × t-1 s=t 0 (U s × X s+1 ) → U t .Then, he establishes a dynamic programming equation, where the Bellman functions are function of the history h t ∈ X t 0 × t-1 s=t 0 (U s × X s+1 ). He identifies cases where no loss of optimality results from reducing the search to Markovian feedbacks X t → U t . In such cases, the Bellman functions are function of the state x t ∈ X t , and the minimization in the dynamic programming equation is done over controls u t ∈ U t . The main objective of Puterman is to explore infinite horizon criteria, average reward criteria, the continuous time case, and to present many examples.Hernández-Lerma and Lasserre approach The ingredients of the approach developed in [17, §2.2, §3.2, §3.3] are the following:1. time t ∈ t 0 , T is discrete and runs among a finite set of consecutive integers; 2. (X t 0 , X t 0 ), . . . , (X T , X T ) are Borel spaces (state spaces); 3. (U t 0 , U t 0 ),. . . , (U T -1 , U T -1 ) are Borel spaces (control spaces); there are also feasible state-dependent control constraints that we do not present here;4. ν t:t+1 : X t ×U t → ∆(X t+1 ), for t ∈ t 0 , T -1 , are Borel-measurable stochastic kernels (transitions); 5. L t : X t × U t → R, for t ∈ t 0 , T -1 , and K : X T → R are Borel-measurable functions (instantaneous and final costs).

  for t ∈ t 0 , T -1 , are Borel-measurable mappings (dynamics);6. ρ t:t+1 : X t × U t → ∆(W t+1 ), for t ∈ t 0 , T -1 ,are Borel-measurable stochastic kernels (noise distributions); 7. L t : X t × U t → R, for t ∈ t 0 , T -1 , and K : X T → R are lower semianalytic functions (instantaneous and final costs).

  are the indices of multiple consecutive time blocks t 0 , t 1 , . . . , t N -1 , t N , with N ≥ 1 an integer; 7. (X t j , X t j ) j∈ 0,N are measurable spaces (time block state spaces); 8. θ t 0 : W t 0 → X t 0 and θ t j : W t 0 ×

		t j -1 s=t 0 (U s × W s+1 ) → X t j	j∈ 1,N	are measur-
	able mappings (time block reduction of history towards state);
	9. f t j :t j+1 : X t j ×	t j+1 -1 s=t j (U s × W s+1 ) → X t j+1	j∈ 0,N -1	are measurable mappings
	(time block dynamics).

  are Bellman functions, in that they are solution of a Bellman or dynamic programming equation. For t in 0, T , let L 0 + (H t , H t ) be the space of universally measurable nonnegative numerical functions over H t (see [5, § 7.7] for further details). For t in 0, T -1 , we define the Bellman operator B t+1:t by, for all φ ∈ L 0 + (H t+1 , H t+1 ), , u t , w t+1 )ρ t:t+1 (dw t+1 | h t ) , ∀h t ∈ H t . t+1 , H t+1 ), we have that B t+1:t φ is a well defined nonnegative numerical function. The proof of the following theorem is given in Appendix A. Theorem 1. Assume that all the spaces introduced in §9.2.2 are Borel spaces, the stochastic kernels in (9.1) are Borel-measurable, and that the criterion j in (9.2) is a nonnegative lower semianalytic numerical function. Then, the Bellman operators in (9.5) are such that B t+1:t : L 0 + (H t+1 , H t+1 ) → L 0 + (H t , H t ), and the value functions V t defined in (9.3) are universally measurable and satisfy the Bellman equation, or (stochastic) dynamic programming equation,

	B t+1:t φ (h t ) = inf ut∈Ut W t+1	φ(h t (9.5)
	Since φ ∈ L 0 + (H

  Figure 9.1: Commutative diagrams in case of state reduction To prepare a dynamic programming equation, we define the Bellman operator across (t : r) B t:r : L 0 + (H t , H t ) → L 0 + (H r , H r ) by

	r
	θ t	θ r
	B t:r
	1

  Proposition 3 can easily be extended to the case of multiple consecutive time blockst i , t i+1 , with N ∈ N * , i ∈ 0, N -1 and 0 = t 0 < • • • < t N = T .Definition 4. Let {(X t i , X t i )} i∈ 0,N be a family of measurable state spaces, {θ t i } i∈ 0,N be a family of measurable reduction mappings θ t i : H t i → X t i , and f t i :t i+1 i∈ 0,N -1 be a family of measurable dynamics f t i :t i+1 :X t i × H t i +1:t i+1 → X t i+1 . The triplet ({X t i } i∈ 0,N , {θ t i } i∈ 0,N , {f t i :t i+1 } i∈ 0,N-1 ) is called a state reduction across the consecutive time blocks t i , t i+1 , i ∈ 0, N -1 if every triplet (θ t i , θ t i+1 , f t i :t i+1 ) is a state reduction, for i in 0, N -1 . The state reduction across the consecutive time blocks t i , t i+1 is said to be compatible with the family {ρ s-1:s } s∈ 1,T of stochastic kernels given in (9.1) if every triplet (θ t i , θ t i+1 , f t i :t i+1 ) is compatible with the family {ρ s-1:s } s∈ t i +1,t i+1 , for i in 0, N -1 .

	9.3.2 State reduction on multiple consecutive time blocks
	and dynamic programming equations
	.11)
	The proof of Proposition 3 is given in Appendix A. Proposition 3 can be in-
	terpreted as follows. Denoting by θ ⋆ t : L 0 + (X t , X t ) → L 0 + (H t , H t ) the operator defined by θ ⋆ + (X t , X t ), the relation (9.10) rewrites as t ( φ t ) = φ t • θ t for any φ t ∈ L 0 θ ⋆ t , that is, Proposition 3 states that the diagram in the right part r • B t:r = B t:r • θ ⋆ of Figure 9.1 is commutative.

  of slow time scale and fast time scale state measurable sets. We also suppose given a family {F s s } s∈S\{s} of slow time scale dynamics measurable mappings, that represent the evolution "driven at the slow time scale" given, for s ∈ S \ {s}, by3

	F s s : X s s ×U s s ×W s s + → X sf (s + ,f) , x s s , u s s , w s s + → x sf (s + ,f) = F s s x s s , u s s , w s s + .	(9.22a)
	We suppose given a family {F sf (s,f) }	(s,f)∈S×(F\{f})
	Decisions. We suppose given
	a family {U s s } s∈S\{s} of slow time scale decision measurable sets, and a family {W s s } s∈S of slow time scale uncertainty measurable sets,
	a family {U sf (s,f) } (s,f)∈S×(F\{f}) a family {W sf (s,f) } (s,f)∈S×(F\{f})	of fast time scale decision measurable sets, and of fast time scale uncertainty measurable sets.
	Dynamics. We suppose given a family {X s s } s∈S and a family {X sf (s,f) }	(s,f)∈S×(F\{f})

9.2:

The product timeline with an extra starting point (s -, f)

  f) -→ ρ s s:s + dw sf (s + ,f) {w s s ′ } s≺s ′ ≺s if f = f , ρ sf (s,f):(s,f) + dw sf (s,f) + {w sf (s,f ′ ) } f≺f ′ ≺f if f ̸ = f . (9.30)

  s (x s s ) = inf + ,f):(s + ,f + ) ( dw sf (s + ,f + ) | w s s + ) • • • ):(s + ,f) ( dw sf (s + ,f) | w s s + , w sf (s + ,f + ) , • • • , w sf (s + ,f ) , w sf (s + ,f) ) + V s + F s:s + (x s s , u s s , w s s + , . . . , u sf (s + ,f -) , w sf (s + ,f) ) ,(9.31)where F s:s + is the composition F s:s + = F sf (s + ,f

	u s s ∈U s s	s + W s	ρ s s:s + ( dw s s + )
	inf (s + ,f) u sf ∈U sf (s + ,f) (s inf W sf (s + ,f + ) ρ sf u sf (s + ,f -) ∈U sf (s + ,f -) (s + ,f) W sf	ρ sf (s + ,f	-) )
				Λ s (x s s , u s s , w s s + , . . . , u sf (s + ,f

---)

  [START_REF] Lichtman | Alfred Nobel and His Prizes: From Dynamite to DNA[END_REF] do not depend on any decision variable makes it possible to build a probability ρ (s,f):(s,f) on the product spaceW = γ s {u (s ′ ,f ′ ) , w (s ′ ,f ′ ) + } (s ′ ,f ′ )≺(s,f) , ∀s ∈ S \ {s} , (9.33d) u sf (s,f) = γ (s,f) {u (s ′ ,f ′ ) , w (s ′ ,f ′ ) + } (s ′ ,f ′ )≺(s,f) , ∀s ∈ S , ∀f ∈ F \ {f} . (9.33e)

	Then Problem 9.4 may be rewritten using this probability as
	V s -(x s s -) = inf γ	W (s,f):(s,f)	s∈S	Λ s x s s -, u s s -, w s s , {x sf (s,f) , u sf (s,f) , w sf (s,f) + }
					(s,f)
					(9.33a)
	s.t. x sf (s,f) + = F sf (s,f) (x sf (s,f) , u sf (s,f) , w sf (s,f) (9.33b)
	x sf (s + ,f) = F s s (x s s , u s s , w s s + ) , ∀s ∈ S \ {s} , u s s	(9.33c)

(s,f):(s,f) by

ρ (s,f):(s,f) = s∈S ρ s s:s + ( dw s s + ) ⊗ ρ sf (s + ,f):(s + ,f + ) ( dw sf (s + ,f + ) | w s s + ) ⊗ • • • ⊗ ρ sf (s + ,f -):(s + ,f) ( dw sf (s + ,f) | w s s + , w sf (s + ,f + ) , • • • , w sf (s + ,f -) ) . (9.32) f∈F\{f} + Λ s x s s ρ (s,f):(s,f) dw s s , dw sf (s,f + ) • • • dw sf (s,f -) , dw sf + ) , ∀s ∈ S , ∀f ∈ F \ {f} ,

  9.33e). This leads to a reformulation of Problem 9.33 as a classical stochastic optimal control problem infE s∈S Λ s X s s -, U s s -, W s , {X sf (s,f) , U sf (s,f) , W f (s,f) + } + = F sf (s,f) (X sf (s,f) , U sf (s,f) , W sf (s,f) + ) , ∀s ∈ S , ∀f ∈ F \ {f} , (9.35b) X sf (s + ,f) = F s s X s s , U s s , W s s + , ∀s ∈ S\{s} ,(9.35c)

	f∈F\{f}	+ Λ s X s s
		(9.35a)
	s.t. X sf (s,f) U s s ∈ U s s , ∀s ∈ S , σ(U s	(9.35d)

s ) ⊂ σ({W s s } s ′ ≺s , {W sf (s ′ ,f ′ ) } (s ′ ,f ′ )≺(s,f) ) , ∀s ∈ S ,

(9.35e)

U sf (s,f) ∈ U sf (s,f) , ∀s ∈ S , ∀f ∈ F \ {f} ,

(9.35f)

σ U sf (s,f) ⊂ σ {W s s ′ } s ′ ≺s , {W sf (s ′ ,f ′ ) } (s ′ ,f ′ )≺(s,f) , ∀s ∈ S , ∀f ∈ F \ {f} ,

Table 9 .

 9 1: Identification of the elements introduced in §9.4.1 with elements of the crude oil procurement problem we do not assume that the crude prices are independent week by week, and the possible dependency is modeled by stochastic kernels {ρ sf (s,f):(s,f) + }

f∈F\{f}

.

We could also consider any j : H t → R, measurable bounded function, or measurable and uniformly bounded below function. However, for the sake of simplicity, we will deal in the sequel with measurable nonnegative numerical functions. When j(h T ) = +∞, this materializes joint constraints between uncertainties and controls.

Notice that, if only the couple (θ r , f r:t ) is given, we can define θ t by (9.7c), and thus obtain a triplet (θ r , θ t , f r:t ) which is a state reduction across (r : t).

We stress that the slow time scale dynamics (9.22a) yields as output the first fast state of the slow period (and not the next slow state). Thus, the slow time scale dynamics (9.22a) is not a dynamics from one slow state to the next slow state.

Acknowledgements

When the PhD started, I vowed not to cut my hair until I finished the manuscript.

Acknowledgements. We thank Roger Wets for fruitful discussions about the possibility of mixing stochastic dynamic programming with progressive hedging.

Remark 6 (Block independent exogenous noises and stochastic kernels). Assume that the family {ρ s-1:s } s∈ 1,T of stochastic kernels in §9.2.2 are mappings whose arguments do not include the control part (that is, depend at most on the history uncertainty part (see (A.2a)). If we interpret stochastic kernels as (conditional) distributions of noises (random process), this means that the system dynamics are driven by an exogenous noise process, say (W t ) t∈ 1,T . Moreover, assume that the stochastic kernels give rise to noises that are independent block by block, in the sense that the family (W t ) t∈ t i +1,t i+1 i∈ 0,N -1 is made of independent random vectors, i by i . Then, from Definitions 2 and 4, we deduce that any state reduction across the same time blocks is compatible with the stochastic kernels.

Assuming the existence of a state reduction across the consecutive time blocks t i , t i+1 compatible with the family of stochastic kernels (9.1), we obtain the existence of a family of reduced Bellman operators across the consecutive t i , t i+1 as an immediate consequence of multiple applications of Proposition 3, that is, B t i+1 :t i :

). We now consider the family of optimization problems defined by the associated value functions (9.3). Thanks to the state reductions, we can enounce the following theorem which establishes dynamic programming equations across consecutive time blocks.

Theorem 7 (Time block decomposition). Suppose that all the assumptions of Theorem 1 are satisfied and that a state reduction ({X ti } i∈ 0,N , {θ ti } i∈ 0,N , f ti:ti+1 i∈ 0,N -1 ) exists across the consecutive time blocks t i , t i+1 , i ∈ 0, N -1 , satisfying 0 = t 0 < • • • < t N = T , and which is compatible with the family {ρ s-1:s } s∈ 1,T of stochastic kernels given in (9.1). Assume that there exists a reduced criterion ȷ : X T → [0, +∞] such that the cost function j in (9.2) can be factored as j = ȷ•θ T . We define the family of reduced value functions { V t i } i∈ 0,N by

Then, the family

The proof is an immediate consequence of multiple applications of Theorem 1 and Proposition 3. Then, it is easy, and left to the reader, to prove that the following Corollary holds true.

Corollary 8 (Taking care of instantaneous costs in addition to final cost). Assume that a state reduction on multiple consecutive time blocks compatible with the family of stochastic kernels (as in Definition 4) exists, and that the criterion j : H T → R can be factored as

(9.16)

the timeline associated with Figure 9.4 (notice that we consider that a month is made of 4 weeks). The initial stage (M 0 , 5) corresponds to the additional stage (s -, f) in (9.21). The stages (M 1 , 5) and (M 2 , 5) both represent the "end of the month" when a consumption decision (slow scale decision u s s on the bottom line of Figure 9.4) is taken.

We now illustrate how the crude oil procurement problem can be put in the form of a two time scale optimization problem such as presented in §9.4.1. For this purpose, we proceed to the identifications in Table 9.1.

We call s-buffer (resp. s --buffer), the temporary stock that is created at the beginning of the month s (resp. s -) and that will be delivered two months after. For instance, in Figure 9.4, the yellow disks represent the M 1 -buffer and the red disks represent the M 2 -buffer. We introduce the state variable x sf (s,f) = s --buffer, s-buffer, refinery stocks , together with the accumulation dynamics F sf (s,f) for the buffers, and the accumulation dynamics F s s for the stocks. Supposing that the products prices are independent month by month, we represent this assumption by a family of constant kernels {ρ s s:s + } s∈S\{s} . By contrast,

List of Tables

Appendix A

Technical details and proofs

We introduce the notations

From a history h t ∈ H t , we can extract the (r : s)-history uncertainty part

the (r : s)-history control part (notice that the indices are special)

Flows Let r and t be given such that 0 ≤ r < t ≤ T . For a (r : t -1)-history feedback γ = {γ s } s=r,...,t-1 ∈ Γ r:t-1 , we define the flow Φ γ r:t by

Otherwise stated, the flow is given by

With this convention, the expression Φ γ r:t makes sense when 0 ≤ r ≤ t ≤ T . The mapping Φ γ r:t gives the history at time t as a function of the initial history h r at time r and of the history feedbacks {γ s } s=r,...,t-1 ∈ Γ r:t-1 .

An immediate consequence of this definition are the flow properties:

Φ γ r:t+1 (h r , w r+1:t+1 ) = Φ γ r:t (h r , w r+1:t ), γ t Φ γ r:t (h r , w r+1:t ) , w t+1 , 0 ≤ r ≤ t ≤ T -1 , (A.4a) Φ γ r:t (h r , w r+1:t ) = Φ γ r+1:t (h r , γ r (h r ), w r+1 ), w r+2:t , 0 ≤ r < t ≤ T .

(A.4b) Definition 10. Let r and t be given such that 0 ≤ r ≤ t ≤ T .

When 0 ≤ r < t ≤ T , for a (r : t -1)-history feedback γ = {γ s } s∈ r,t-1 ∈ Γ r:t-1 , and for a family {ρ s-1:s } r+1≤s≤t of stochastic kernels ρ s-1:s : ρ s-1:s dw s Φ γ r:s-1 (h r , w r+1:s-1 ) . (A.5)

The stochastic kernels ρ γ r:t on H t , given by (A.5), are of the form ρ γ r:t ( dh

, where, for each h r ∈ H r , the probability distribution ϱ γ r:t ( dh ′ r+1:t | h r ) only charges the histories visited by the flow from r + 1 to t. The construction of the stochastic kernels ρ γ r:t is developed in [5, p. 190] for relaxed history feedbacks and obtained by using [START_REF] Bertsekas | Stochastic Optimal Control: The Discrete-Time Case[END_REF]Proposition 7.45].

Proposition 11. The family {ρ γ s:t } s=r,...,t of stochastic kernels of Definition 10 has the flow property:

(A.6)

by Fubini Theorem. As the two expressions (A.7a) and (A.7b) are equal for any φ ∈ L 0 + (H t , H t ), we deduce the flow property (A.6).

Proof of Theorem 1

We only give a sketch of the proof, as it is a variation on different results of [START_REF] Bertsekas | Stochastic Optimal Control: The Discrete-Time Case[END_REF], the framework of which we follow.

Proof. We take the history space H t for state space, and the state dynamics

Then, the family {ρ s-1:s } s∈ 1,T of stochastic kernels (9.1) gives a family of disturbance kernels that do not depend on the current control. The criterion to be minimized (9.2) is a function of the history at time T , thus of the state at time T . The optimization problem defined by the associated value function (9.3) is thus a finite horizon model with a final cost and we are minimizing over the so-called state-feedbacks. Then, the proof of Theorem 1 follows from the results developed in Chap. 7, 8 and 10 of [START_REF] Bertsekas | Stochastic Optimal Control: The Discrete-Time Case[END_REF] in a Borel setting. Since we are considering a finite horizon model with a final cost, we detail the steps needed to use the results of [START_REF] Bertsekas | Stochastic Optimal Control: The Discrete-Time Case[END_REF]Chap. 8].

The final cost at time T can be turned into an instantaneous cost at time T -1 by inserting the state dynamics (A.8) in the final cost. Getting rid of the disturbance in the expected cost by using the disturbance kernel is standard practice. Then, we can turn this non-homogeneous finite horizon model into a finite horizon model with homogeneous dynamics and costs by following the steps of [START_REF] Bertsekas | Stochastic Optimal Control: The Discrete-Time Case[END_REF]Chap. 10]. Using [START_REF] Bertsekas | Stochastic Optimal Control: The Discrete-Time Case[END_REF]Proposition 8.2], we obtain that the family of optimization problems defined by the associated value functions (9.3), when minimizing over the relaxed state feedbacks, satisfies the Bellman equation (9.6); we conclude with [START_REF] Bertsekas | Stochastic Optimal Control: The Discrete-Time Case[END_REF]Proposition 8.4] which covers the minimization over state feedbacks.

To summarize, Theorem 1 is valid under the general Borel assumptions of [START_REF] Bertsekas | Stochastic Optimal Control: The Discrete-Time Case[END_REF]Chap. 8] and with the specific (F -) assumption needed for [START_REF] Bertsekas | Stochastic Optimal Control: The Discrete-Time Case[END_REF]Proposition 8.4]; this last assumption is fulfilled here since we have assumed that the criterion (9.2) is nonnegative.

Proof of Proposition 3

Proof. Let φ t : X t → [0, +∞] be a given measurable nonnegative numerical function, and let φ t : H t → [0, +∞] be

(A.9)

Let φ r : H r → [0, +∞] be the measurable nonnegative numerical function obtained by applying the Bellman operator B t:r across (t : r) (see (9.9)) to the measurable nonnegative numerical function φ t :

We show that there exists a measurable nonnegative numerical function φ r :

First, we show by backward induction that, for all s ∈ {r, . . . , t}, there exists a measurable nonnegative numerical function φ s such that φ s (h s ) = φ s (θ r (h r ), h r+1:s ). Second, we prove that the function φ r = φ r satisfies (A.11).

For s = t, we have, by (A.9) and by (9.7c), that φ t (h t ) = φ t θ t (h t ) = φ t f r:t (θ r (h r ), h r+1:t ) , so that the measurable nonnegative numerical function φ t is given by φ t • f r:t .

Assume that, at s+1, the result holds true, that is, φ s+1 (h s+1 ) = φ s+1 (θ r (h r ), h r+1:s+1 ). Then, by (A. The induction implies that, at time r, the expression of φ r (h r ) is φ r (h r ) = φ r θ r (h r ) , since the term h r+1:r vanishes. Choosing φ r = φ r gives the expected result.