[pt] A programação estocástica dois estágios é uma abordagem matemática amplamente usada em aplicações da vida real, como planejamento da operação de sistemas de energia, cadeias de suprimentos, logística, gerenciamento de inventário e planejamento financeiro. Como a maior parte desses problemas não pode ser resolvida analiticamente, os tomadores de decisão utilizam métodos numéricos para obter uma solução quase ótima. Em algumas aplicações, soluções não convergidas e, portanto, sub-ótimas terminam sendo implementadas devido a limitações de tempo ou esforço computacional. Nesse contexto, os métodos existentes fornecem uma solução otimista sempre que a convergência não é atingida. As soluções otimistas geralmente geram altos níveis de arrependimento porque subestimam os custos reais na função objetivo aproximada. Para resolver esse problema, temos desenvolvido duas metodologias de solução conservadora para problemas de programação linear estocástica dois estágios com incerteza do lado direito e suporte retangular: Quando a verdadeira distribuição de probabilidade da incerteza é conhecida, propomos um problema DRO (Distributionally Robust Optimization) baseado em esperanças condicionais adaptadas à uma partição do suporte cuja complexidade cresce exponencialmente com a dimensionalidade da incerteza; Quando apenas observações históricas da incerteza estão disponíveis, propomos um problema de DRO baseado na métrica de Wasserstein a fim de incorporar ambiguidade sobre a real distribuição de probabilidade da incerteza. Para esta última abordagem, os métodos existentes dependem da enumeração dos vértices duais do problema de segundo estágio, tornando o problema DRO intratável em aplicações práticas. Nesse contexto, propomos esquemas algorítmicos para lidar com a complexidade computacional de ambas abordagens. Experimentos computacionais são apresentados para o problema do fazendeiro, o problema de alocação de aviões, e o problema do planejamento da operação do sistema elétrico (unit ommitmnet problem). / [en] Two-stage stochastic programming is a mathematical framework widely used in real-life applications such as power system operation planning, supply chains, logistics, inventory management, and financial planning. Since most of these problems cannot be solved analytically, decision-makers make use of numerical methods to obtain a near-optimal solution. Some applications rely on the implementation of non-converged and therefore sub-optimal solutions because of computational time or power limitations. In this context, the existing methods provide an optimistic solution whenever convergence is not attained. Optimistic solutions often generate high disappointment levels because they consistently underestimate the actual costs in the approximate objective function. To address this issue, we have developed two conservative-solution methodologies for two-stage stochastic linear programming problems with right-hand-side uncertainty and rectangular support: When the actual data-generating probability distribution is known, we propose a DRO problem based on partition-adapted conditional expectations whose complexity grows exponentially with the uncertainty dimensionality; When only historical observations of the uncertainty are available, we propose a DRO problem based on the Wasserstein metric to incorporate ambiguity over the actual data-generating probability distribution. For this latter approach, existing methods rely on dual vertex enumeration of the second-stage problem rendering the DRO problem intractable in practical applications. In this context, we propose algorithmic schemes to address the computational complexity of both approaches. Computational experiments are presented for the farmer problem, aircraft allocation problem, and the stochastic unit commitment problem.

Hydropower in Sweden is a powerful and efficient source of energy due to its flexibility, usually used to balance the Swedish power system. With the transition of power system into more intermittent power sources, the role of hydro-power as producers will become more important. Thus the optimal scheduling of hydropower units, with other assets, holds an important place in electric power systems, which is significantly investigated as a research issue. This thesis presents an optimization model that aims at maximizing the income of that producer. The model is implemented on a virtual power plant trading in both day-ahead and mFRR balancing markets in the SE2 bidding zone in Sweden. The virtual power plant comprises hydo-power plants located on the Swedish river Skellefteälven, a wind power unit, and a storage unit. This system participates in electricity market as a single entity in order to optimize the use of energy resources. As feature, uncertainty in electricity market price, wind power production and in active-time duration in the mFRR energy market are modeled in order to formulate a so-called stochastic adaptive robust optimization model. The latter is solved using a column-and-constraint generation algorithm, solved by GAMS and Matlab. A bid curve analysis is performed showing the optimal strategy in case of low/high price scenario and the level of conservativeness. After that, a revenue assessment is carried out which in turn leads to an investigation of the interaction between the three assets and the impact of the storage facility in the revenue. Results demonstrate the advantage of the battery in increasing profit in some cases and its flexibility in the use of storing energy and selling it to the markets at suitable times, e.g., it saves energy from the wind in hours of comparatively low prices, while it sells it in hours of comparatively high prices. Finally, an assessment on variation of imbalance costs is held with and without battery, comparing how such virtual power plants reduce the imbalance costs. / Vattenkraften i Sverige är en kraftfull och effektiv energikälla tack vare sin flexibilitet, används vanligtvis för att balansera det svenska kraftsystemet. I och med att kraftsystemet övergår till mer intermittenta energikällor kommer vattenkraftens roll som producent att bli viktigare. Den optimala schemaläggningen av vattenkraftsenheter har därför tillsammans med andra tillgångar en viktig plats i elkraftsystemen, vilket är en viktig forskningsfråga. I denna avhandling presenteras en optimeringsmodell som syftar till att maximera inkomsten för den producenten. Modellen implementeras på ett virtuellt kraftverk som handlar på både day-ahead- och mFRR-balanseringsmarknader i budzonen SE2 i Sverige. Det virtuella kraftverket består av vattenkraftverk belägna vid den svenska Skellefteälven, en vindkraftsenhet och en lagringsenhet. Systemet deltar på elmarknaden som en enda enhet för att optimera användningen av energiresurser. Som en funktion kan osäkerheten i elmarknadspriset, vindkraftsproduktionen och den aktiva tiden i kraftverket användas. mFRR-marknaden modelleras för att formulera en så kallad stokastisk adaptiv robust optimeringsmodell. Den sistnämnda löses med hjälp av en kolumn-och-bindningsgenerering algoritm, som löses med GAMS och Matlab. En analys av budkurvan utförs och visar att optimala strategin vid scenarier med lågt/hög pris och nivån av försiktighet. Efter därefter görs en intäktsbedömning som i sin tur leder till en undersökning av interaktionen mellan de tre tillgångarna och lagringsanläggningens inverkan på intäkterna.Resultaten visar att batteriet i vissa fall är en fördel när det gäller att öka vinsten och att dess flexibilitet när det gäller att lagra energi och sälja den på marknaden vid lämpliga tidpunkter, Det sparar t.ex. energi från vinden under timmar med jämförelsevis låga priser, medan det säljer den. när priserna är jämförelsevis höga. Slutligen görs en bedömning av variationen i obalansen. med och utan batteri, där man jämför hur sådana virtuella kraftverk minskar kostnaderna för obalans.

[pt] A complementaridade entre os perfis de geração renovável tem sido amplamente explorada na literatura. No entanto, as estruturas regulatórias eeconômicas para usinas híbridas de energia apresentam desafios e oportunidades interessantes para investidores, reguladores e planejadores. Focando nomercado de energia brasileiro, este artigo propõe um cálculo unificado e isonômico de Garantia Física (GF) para geradores renováveis não controláveis, quenos permite 1) generalizar o conceito de GF para unidades híbridas e 2) capturar as sinergias regulatórias e econômicas entre as fontes. Com base na GFnão discriminatória proposta para usinas híbridas de energia, a co-otimizaçãodas estratégias de contratação de energia no mercado de futuro e da rede, o Montante de Uso do Sistema de Transmissão (MUST), é estudada, e seus incentivos econômicos são demonstrados. A participação ótima de fontes renováveisque compõem a geração da usina híbrida também é considerada no modelo eanalisada em nossos estudos de caso. Com base em dados reais do mercadode energia brasileiro, quantificamos os benefícios das estruturas e modelos demercado propostos para uma unidade híbrida típica de eólico-solar. / [en] The complementarity between renewable generation profiles has been widely explored in literature. Notwithstanding, the regulatory and economic frameworks for hybrid power plants add interesting challenges and opportunities for investors, regulators, and planners. Focusing on the Brazilian power market, this paper proposes a unified and isonomic firm energy certificate (FEC) calculation for non-controllable renewable generators, which allows us to 1) generalize the FEC concept for hybrid units and 2) capture the regulatory and economic synergies between sources. Based on the non-discriminatory FEC proposed for hybrid power plants, the co-optimization of both forward-market and network-access contracting strategies is studied, and its economic incentives are demonstrated. The optimal share of renewable sources composing the hybrid power plant is also considered in the model and analyzed in our case studies. Based on real data from the Brazilian power market, we quantify the benefits of the proposed market structures and model for a typical wind–solar hybrid unit.

[pt] Esta tese é composta por quatro artigos que descrevem diferentes formas de inclusão de aversão a risco em problemas dinâmicos, ressaltando seus aspectos teóricos e consequências práticas envolvidas em técnicas de otimização sob incerteza aplicadas a problemas financeiros. O primeiro artigo propões uma interpretação econômica e analisa as consequencias práticas da consistência temporal, em que particular para o problema de seleção de portfólio. No segunfo artigo, também aplicado à seleção de portfólio, é proposto um modelo que considera empréstimo como variável de decisão e uma função convexa e linear por partes que representa a existência de diversos credores com diferentes limites de crédito e taxas de juros. A performance do modelo proposto é melhor que as aproximações existentes e garante otimalidade para a situação de vários credores. No terceiro artigo, desenvolve-se um modelo de emissão de títulos de dívida de uma empresa que seja financiar um conjunto pré-determinado de projetos. Trata-se de um modelo de otimização dinâmico sob incerteza que considera títulos pré e pós-fixados com diferentes maturidades e formas de amortização. As principais contribuições são o tratammento de um horizonte longuíssimo prazo através de uma estrutura híbrida dos cenários; a modelagem detalhada do pagamento de cupons e amortizações; o desenvolvimento de uma função objetivo multi-critério que reflete o trade-off entre risco-retorno além de outras medidas de performance financeiras como a taxa de alavancagem (razão passivos sobre ativos). No quarto artigo é desenvolvido um modelo de programação estocástica multi-estágio para obter a política ótima de caixa de uma empresa cujo custo de investimento e o custo da dívida são incertos e modelados em diferentes regimes. As contribuições são a extensão de metodologia de equilíbrio dual para um modelo estocástico; a proposição de uma regra de decisão baseada na estrutura de regime dos fatores de risco que aproxima de forma satisfatória o modelo original. / [en] This PhD Thesis is composed of four working papers, each one with a respective chapter on this thesis, with contributions on risk averse stochastic programming models. In particular, it focuses on analyzing the practical consequences of certain theoretical concepts of decision theory, finance and optimization. The first working paper analyzes the practical consequences and the economic interpretation of time consistent optimal policies, in particular for well known portfolio selection problem. The second paper has also a contribution to the portfolio selection literature. Indeed, we develop leverage optimal strategy considering a single-period debt with a piecewise linear borrowing cost function, which represents the actual situation faced by investors, and show a significant gap in comparison to the suboptimal solutions obtained by the usual linear approximation. Moreover, we develop a multistage extension where our cost function indirectly penalizes the excess of leverage, which is closely related to the contribution of the next working paper. The contribution of the third working paper is to penalize excess of leverage in a debt issuance multistage model that optimizes over several types of bonds with fixed or floating rate, different maturities and amortization patterns. For the sake of dealing with the curse of dimensionality of a long term problem, we divide the planning horizon into a detailed part at the beginning followed by a policy rule approximation for the remainder. Indeed, our approximation mitigates the end effects of a truncated model which is closely related to the contributions of the forth working paper. The forth paper develops a multistage model that seeks to obtain the optimal cash holding policy of a firm. The main contributions are a methodology to end effect treatment for a multistage model with infinite horizon and the development of a policy rule as approximation of the optimal solution.

The work presented in this dissertation has been focused on exploiting the branch-and-price (BNP) method for the solution of various stochastic mixed integer programming problems (MIPs). In particular, we address the stochastic generalized assignment problem (SGAP), a hospital staff scheduling problem (HSSP), a stochastic hospital staff scheduling problem (SHSSP), and a stochastic short-term personnel planning problem (SSTPP). The BNP method has been developed in concert with the dual stabilization technique and other enhancements of this method for each of these problems. In view of an excessive number of scenarios that arise for these problems, we also implement the Monte Carlo method within the BNP scheme. The superiority of the BNP-based method over the branch-and-cut (BNC) method is demonstrated for all of these problems. The first problem that we address is the SGAP for which the processing time of a job on a machine is assumed to be stochastic. Even though the generalized assignment problem (GAP) has been solved using the BNP method, yet no study has been reported in the literature on the use of the BNP method for the solution of the SGAP. Our work has been motivated by the desire to fill this gap. We begin by showing that it is better to solve the SGAP as a stochastic program in contrast to solving it by using the expected values of the times required to process the jobs on the machines. Then, we show that the stochastic model of the SGAP is a complete recourse model — a useful property which permits the first stage decisions to produce feasible solutions for the recourse problems. We develop three BNP-based methods for the solution of the SGAP. The first of these is BNP-SGAP, which is a combination of branch-and-bound and column generation methods. The pricing problem of BNP-SGAP is separable with regard to each machine, and it is a multiple-constraint knapsack problem. The second method is BNP-SGAP implemented in concert with the dual stabilization technique (DST), and it is designated as BNPDST-SGAP. We have introduced a new DST by modifying the Boxstep method of Pigatti et al. [76]. We have shown that our method performs better than the method of Pigatti et al. [76] resulting in over two-fold savings in cpu times on average. The third method that we develop for the solution of the SGAP is BNPDST-SGAP implemented with an advanced start to obtain an initial feasible solution. We use a greedy heuristic to obtain this solution, and this heuristic is a modification of a similar method used for the knapsack problem. It relies on the information available at a node of the underlying branch-and-bound tree. We have shown that this procedure obtains an initial feasible solution, if it exists at that node. We designate this method as BNPDSTKP-SGAP. We have also developed a BNC method to solve the SGAP using CPLEX 9.0. We have compared the performances of the BNP and BNC methods on various problem instances obtained by varying the number of machines, the ratio of the number of machines to the number of jobs, the machine capacity, and the penalty cost per unit of extra resource required at each machine. Our results show that all BNP-based methods perform better than the BNC method, with the best performance obtained for BNPDSTKP-SGAP. An issue with the use of the scenario-based methods that we have employed for the solution of the SGAP is that the number of scenarios generally grows exponentially in problem parameters, which gives rise to a large-size problem. To overcome the complexity caused by the presence of a large number of scenarios for the solution of the SGAP, we introduce the use of the Monte Carlo method (MCM) within the BNP scheme. We designate this method as BNPDSTKP-SGAP with MCM. It affords the use of a small subset of scenarios at a time to estimate the "true" optimal objective function value. Replications of the subsets of scenarios are carried out until the objective function value satisfies a stopping criterion. We have established theoretical results for the use of the MCM. These pertain to determining unbiased estimates of: (i) lower and upper bounds of the "true" optimal objective function value, (ii) the "true" optimal solution, and (iii) the optimality gap. We have also provided the 100(1-ï ¡) confidence interval on the optimality gap. Our experimental investigation has shown the efficacy of using this method. It obtains almost optimal solutions, with the objective function value lying within 5% of the "true" optimal objective function value, while giving almost ten-fold savings in cpu time. Our experimentation has also revealed that an increment in the number of scenarios in each replication makes a greater impact on the quality of the solution obtained than an increment in the number of replications. We have also observed the impact of a change in the variance of a processing time distribution on cpu time. As expected, the optimal objective function value increases with increment in processing time variability. Also, by comparing the results with the expected value solution, it is observed that the greater the variability in the data, the better it is to use the stochastic program. The second problem that we study is the hospital staff scheduling problem. We address the following three versions of this problem: HSSP (General): Implementation of schedule incorporating the four principal elements, namely, surgeons, operations, operating rooms, and operation times; HSSP (Priority): Inclusion of priority for some surgeons over the other surgeons regarding the use of the facility in HSSP (General); HSSP (Pre-arranged): Implementation of a completely pre-fixed schedule for some surgeons. The consideration of priority among the surgeons mimics the reality. Our BNP method for the solution of these problems is similar to that for the SGAP except for the following: (i) a feasible solution at a node is obtained with no additional assignment, i.e., it consists of the assignments made in the preceding nodes of that node in the branch-and-bound tree; (ii) the columns with positive reduced cost are candidates for augmentation in the CGM; and (iii) a new branching variable selection strategy is introduced, which selects a fractional variable as a branching variable by fixing a value of which we enforce the largest number of variables to either 0 or 1. The priority problem is separable in surgeons. The results of our experimentation have shown the efficacy of using the BNP-based method for the solution of each HSSP as it takes advantage of the inherent structure of each of these problems. We have also compared their performances with that of the BNC method developed using CPLEX. For the formulations HSSP (General), HSSP (Priority), and HSSP (Pre-arranged), the BNP method gives better results for 22 out of 30, 29 out of 34, and 20 out 32 experiments over the BNC method, respectively. Furthermore, while the BNC method fails to obtain an optimal solution for 15 experiments, the BNP method obtains optimal solutions for all 96 experiments conducted. Thus, the BNP method consistently outperforms the BNC method for all of these problems. The third problem that we have investigated in this study is the stochastic version of the HSSP, designated as the Stochastic HSSP (SHSSP), in which the operation times are assumed to be stochastic. We have introduced a formulation for this formulation, designated as SHSSP2 (General), which allows for overlapping of schedules for surgeons and operating rooms, and also, allows for an assignment of a surgeon to perform an operation that takes less than a pre-arranged operation time, but all incurring appropriate penalty costs. A comparison of the solution of SHSSP2 (General) and its value with those obtained by using expected values (the corresponding problem is designated as Expected-SHSSP2 (General)) reveals that Expected-SHSSP2 (General) may end up with inferior and infeasible schedules. We show that the recourse model for SHSSP2 (General) is a relatively complete recourse model. Consequently, we use the Monte Carlo method (MCM) to reduce the complexity of solving SHSSP2 (General) by considering fewer scenarios. We employ the branch-and-cut (BNC) method in concert with the MCM for solving SHSSP2 (General). The solution obtained is evaluated using tolerance ratio, closeness to optimality, length of confidence interval, and cpu time. The MCM substantially reduces computational effort while producing almost optimal solutions and small confidence intervals. We have also considered a special case of SHSSP2 (General), which considers no overlapping schedules for surgeons and operating rooms and assigns exactly the same operation time for each assignment under each scenario, and designate it as SHSSP2 (Special). With this, we consider another formulation that relies on the longest operation time among all scenarios for each assignment of a surgeon to an operation in order to avoid scheduling conflicts, and we designate this problem as SHSSP (Longest). We show SHSSP (Longest) to be equivalent to deterministic HSSP, designated as HSSP (Equivalent), and we further prove it to be equivalent to SHSSP (General) in terms of the optimal objective function value and the optimal assignments of operations to surgeons. The schedule produced by HSSP (Equivalent) does not allow any overlap among the operations performed in an operating room. That is, a new operation cannot be performed if a previous operation scheduled in that room takes longer than expected. However, the schedule generated by HSSP (Equivalent) may turn out to be a conservative one, and may end up with voids due to unused resources in case an operation in an operating room is completed earlier than the longest time allowed. Nevertheless, the schedule is still a feasible one. In such a case, the schedule can be left-shifted, if possible, because the scenarios are now revealed. Moreover, such voids could be used to perform other procedures (e.g., emergency operations) that have not been considered within the scope of the SHSSP addressed here. Besides, such a schedule can provide useful guidelines to plan for resources ahead of time. The fourth problem that we have addressed in this dissertation is the stochastic short-term personnel planning problem, designated as Stochastic STPP (SSTPP). This problem arises due to the need for finding appropriate temporary contractors (workers) to perform requisite jobs. We incorporate uncertainty in processing time or amount of resource required by a contractor to perform a job. Contrary to the SGAP, the recourse model for this problem is not a relatively complete recourse model. As a result, we cannot employ a MCM method for the solution of this problem as it may give rise to an infeasible solution. The BNP method for the SSTPP employs the DST and the advanced start procedure developed for the SGAP, and due to extra constraints and presence of binary decision variables, we use the branching variable selection strategy developed for the HSSP models. Because of the distinctive properties of the SSTPP, we have introduced a new node selection strategy. We have compared the performances of the BNC-based and BNP-based methods based on the cpu time required. The BNP method outperforms the BNC method in 75% of the experiments conducted, and the BNP method is found to be quite stable with smaller variance in cpu times than those for the BNC method. It affords solution of difficult problems in smaller cpu times than those required for the BNC method. / Ph. D.

Multiobjective Stochastic Linear Programming is a relevant topic. As a matter of fact, many real life problems ranging from portfolio selection to water resource management may be cast into this framework. There are severe limitations in objectivity in this field due to the simultaneous presence of randomness and conflicting goals. In such a turbulent environment, the mainstay of rational choice does not hold and it is virtually impossible to provide a truly scientific foundation for an optimal decision. In this thesis, we resort to the bounded rationality and chance-constrained principles to define satisficing solutions for Multiobjective Stochastic Linear Programming problems. These solutions are then characterized for the cases of normal, exponential, chi-squared and gamma distributions. Ways for singling out such solutions are discussed and numerical examples provided for the sake of illustration. Extension to the case of fuzzy random coefficients is also carried out. / Decision Sciences

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

L'objectif de cette recherche est de développer des modèles aussi bien conceptuels, analytiques et managériaux en analysant un maillon de la supply chain, à savoir la relation entre un distributeur et deux fournisseurs opérant dans un environnement incertain. Dans la première partie de la thèse, nous considérons un seul produit, plutôt haut de gamme et/ou périssable, et nous faisons l’analyse sur un horizon d’une période. Dans ce cas précis, les caractéristiques unitaires du produit sont toutes non linéaires, à savoir : le prix, le coût de production, le coût de rupture, le coût de reprise. La demande est supposée être une variable aléatoire. Dans la deuxième partie de la thèse, nous nous inspirons des pratiques de firmes internationales qui s’approvisionnent, pour une partie de leur offre, dans des pays à bas coûts. Nous développons plusieurs modèles mais dont la structure de base est similaire, à savoir : deux produits (un haut gamme acheté localement et l’autre bas de gamme acheté dans les pays à bas coûts), un horizon de trois périodes, deux fournisseurs à capacité de production limitée et un distributeur ayant des capacités de stockage limitées. Une panoplie de résultats théoriques, numériques ainsi que des insights sont présentés.Les modèles développés peuvent être utilisés comme des outils d’aide { la prise de décision dans les environnements décrits dans cette thèse / The objective of this research is to develop conceptual, analytical, and managerial models and insights by analyzing a portion of the supply chain made up of a retailer dealing with two suppliers in an uncertain environment. In the first part of this thesis, we consider a single high-end (or perishable) product, single period, variable unit price, variable unit production cost, variable unit shortage cost, variable unit salvagevalue, stochastic demand problem. In a second part of the thesis, we consider settings inspired by the case of large international companies sourcing some of their products from low cost countries. This structure is as follows: two products (one sourced locally and the other sourced abroad), a three-period, two-stages, two capacitated suppliers, and a single capacitated retailer. Both analytical and numerical results are provided. Important theoretical results and insights are developed for these types of settings. These models can be used as decision-making aid tools in such environments

Dans cette thèse, nous étudions trois types de problèmes stochastiques : les problèmes avec contraintes probabilistes, les problèmes distributionnellement robustes et les problèmes avec recours. Les difficultés des problèmes stochastiques sont essentiellement liées aux problèmes de convexité du domaine des solutions, et du calcul de l’espérance mathématique ou des probabilités qui nécessitent le calcul complexe d’intégrales multiples. A cause de ces difficultés majeures, nous avons résolu les problèmes étudiées à l’aide d’approximations efficaces.Nous avons étudié deux types de problèmes stochastiques avec des contraintes en probabilités, i.e., les problèmes linéaires avec contraintes en probabilité jointes (LLPC) et les problèmes de maximisation de probabilités (MPP). Dans les deux cas, nous avons supposé que les variables aléatoires sont normalement distribués et les vecteurs lignes des matrices aléatoires sont indépendants. Nous avons résolu LLPC, qui est un problème généralement non convexe, à l’aide de deux approximations basée sur les problèmes coniques de second ordre (SOCP). Sous certaines hypothèses faibles, les solutions optimales des deux SOCP sont respectivement les bornes inférieures et supérieures du problème du départ. En ce qui concerne MPP, nous avons étudié une variante du problème du plus court chemin stochastique contraint (SRCSP) qui consiste à maximiser la probabilité de la contrainte de ressources. Pour résoudre ce problème, nous avons proposé un algorithme de Branch and Bound pour calculer la solution optimale. Comme la relaxation linéaire n’est pas convexe, nous avons proposé une approximation convexe efficace. Nous avons par la suite testé nos algorithmes pour tous les problèmes étudiés sur des instances aléatoires. Pour LLPC, notre approche est plus performante que celles de Bonferroni et de Jaganathan. Pour MPP, nos résultats numériques montrent que notre approche est là encore plus performante que l’approximation des contraintes probabilistes individuellement.La deuxième famille de problèmes étudiés est celle relative aux problèmes distributionnellement robustes où une partie seulement de l’information sur les variables aléatoires est connue à savoir les deux premiers moments. Nous avons montré que le problème de sac à dos stochastique (SKP) est un problème semi-défini positif (SDP) après relaxation SDP des contraintes binaires. Bien que ce résultat ne puisse être étendu au cas du problème multi-sac-à-dos (MKP), nous avons proposé deux approximations qui permettent d’obtenir des bornes de bonne qualité pour la plupart des instances testées. Nos résultats numériques montrent que nos approximations sont là encore plus performantes que celles basées sur les inégalités de Bonferroni et celles plus récentes de Zymler. Ces résultats ont aussi montré la robustesse des solutions obtenues face aux fluctuations des distributions de probabilités. Nous avons aussi étudié une variante du problème du plus court chemin stochastique. Nous avons prouvé que ce problème peut se ramener au problème de plus court chemin déterministe sous certaine hypothèses. Pour résoudre ce problème, nous avons proposé une méthode de B&B où les bornes inférieures sont calculées à l’aide de la méthode du gradient projeté stochastique. Des résultats numériques ont montré l’efficacité de notre approche. Enfin, l’ensemble des méthodes que nous avons proposées dans cette thèse peuvent s’appliquer à une large famille de problèmes d’optimisation stochastique avec variables entières. / In this thesis, we studied three types of stochastic problems: chance constrained problems, distributionally robust problems as well as the simple recourse problems. For the stochastic programming problems, there are two main difficulties. One is that feasible sets of stochastic problems is not convex in general. The other main challenge arises from the need to calculate conditional expectation or probability both of which are involving multi-dimensional integrations. Due to the two major difficulties, for all three studied problems, we solved them with approximation approaches.We first study two types of chance constrained problems: linear program with joint chance constraints problem (LPPC) as well as maximum probability problem (MPP). For both problems, we assume that the random matrix is normally distributed and its vector rows are independent. We first dealt with LPPC which is generally not convex. We approximate it with two second-order cone programming (SOCP) problems. Furthermore under mild conditions, the optimal values of the two SOCP problems are a lower and upper bounds of the original problem respectively. For the second problem, we studied a variant of stochastic resource constrained shortest path problem (called SRCSP for short), which is to maximize probability of resource constraints. To solve the problem, we proposed to use a branch-and-bound framework to come up with the optimal solution. As its corresponding linear relaxation is generally not convex, we give a convex approximation. Finally, numerical tests on the random instances were conducted for both problems. With respect to LPPC, the numerical results showed that the approach we proposed outperforms Bonferroni and Jagannathan approximations. While for the MPP, the numerical results on generated instances substantiated that the convex approximation outperforms the individual approximation method.Then we study a distributionally robust stochastic quadratic knapsack problems, where we only know part of information about the random variables, such as its first and second moments. We proved that the single knapsack problem (SKP) is a semedefinite problem (SDP) after applying the SDP relaxation scheme to the binary constraints. Despite the fact that it is not the case for the multidimensional knapsack problem (MKP), two good approximations of the relaxed version of the problem are provided which obtain upper and lower bounds that appear numerically close to each other for a range of problem instances. Our numerical experiments also indicated that our proposed lower bounding approximation outperforms the approximations that are based on Bonferroni's inequality and the work by Zymler et al.. Besides, an extensive set of experiments were conducted to illustrate how the conservativeness of the robust solutions does pay off in terms of ensuring the chance constraint is satisfied (or nearly satisfied) under a wide range of distribution fluctuations. Moreover, our approach can be applied to a large number of stochastic optimization problems with binary variables.Finally, a stochastic version of the shortest path problem is studied. We proved that in some cases the stochastic shortest path problem can be greatly simplified by reformulating it as the classic shortest path problem, which can be solved in polynomial time. To solve the general problem, we proposed to use a branch-and-bound framework to search the set of feasible paths. Lower bounds are obtained by solving the corresponding linear relaxation which in turn is done using a Stochastic Projected Gradient algorithm involving an active set method. Meanwhile, numerical examples were conducted to illustrate the effectiveness of the obtained algorithm. Concerning the resolution of the continuous relaxation, our Stochastic Projected Gradient algorithm clearly outperforms Matlab optimization toolbox on large graphs.

Diese Arbeit leistet Beiträge zu zwei Gebieten der mathematischen Programmierung: stochastische Optimierung und gemischt-ganzzahlige nichtlineare Optimierung (MINLP). Im ersten Teil erweitern wir quantitative Stetigkeitsresultate für zweistufige stochastische gemischt-ganzzahlige lineare Programme auf Situationen in denen Unsicherheit gleichzeitig in den Kosten und der rechten Seite auftritt, geben eine ausführliche Übersicht zu Dekompositionsverfahren für zwei- und mehrstufige stochastische lineare und gemischt-ganzzahlig lineare Programme, und diskutieren Erweiterungen und Kombinationen des Nested Benders Dekompositionsverfahrens und des Nested Column Generationsverfahrens für mehrstufige stochastische lineare Programme die es erlauben die Vorteile sogenannter rekombinierender Szenariobäume auszunutzen. Als eine Anwendung dieses Verfahrens betrachten wir die optimale Zeit- und Investitionsplanung für ein regionales Energiesystem unter Einbeziehung von Windenergie und Energiespeichern. Im zweiten Teil geben wir eine ausführliche Übersicht zum Stand der Technik bzgl. Algorithmen und Lösern für MINLPs und zeigen dass einige dieser Algorithmen innerhalb des constraint integer programming Softwaresystems SCIP angewendet werden können. Letzteres erlaubt uns die Verwendung schon existierender Technologien für gemischt-ganzzahlige linear Programme und constraint Programme für den linearen und diskreten Teil des Problems. Folglich konzentrieren wir uns hauptsächlich auf die Behandlung der konvexen und nichtkonvexen nichtlinearen Nebenbedingungen mittels Variablenschrankenpropagierung, äußerer Approximation und Reformulierung. In einer ausführlichen numerischen Studie untersuchen wir die Leistung unseres Ansatzes anhand von Anwendungen aus der Tagebauplanung und des Aufbaus eines Wasserverteilungssystems und mittels verschiedener Vergleichstests. Die Ergebnisse zeigen, dass SCIP ein konkurrenzfähiger Löser für MINLPs geworden ist. / This thesis contributes to two topics in mathematical programming: stochastic optimization and mixed-integer nonlinear programming (MINLP). In the first part, we extend quantitative continuity results for two-stage stochastic mixed-integer linear programs to include situations with simultaneous uncertainty in costs and right-hand side, give an extended review on decomposition algorithm for two- and multistage stochastic linear and mixed-integer linear programs, and discuss extensions and combinations of the Nested Benders Decomposition and Nested Column Generation methods for multistage stochastic linear programs to exploit the advantages of so-called recombining scenario trees. As an application of the latter, we consider the optimal scheduling and investment planning for a regional energy system including wind power and energy storages. In the second part, we give a comprehensive overview about the state-of-the-art in algorithms and solver technology for MINLPs and show that some of these algorithm can be applied within the constraint integer programming framework SCIP. The availability of the latter allows us to utilize the power of already existing mixed integer linear and constraint programming technologies to handle the linear and discrete parts of the problem. Thus, we focus mainly on the domain propagation, outer-approximation, and reformulation techniques to handle convex and nonconvex nonlinear constraints. In an extensive computational study, we investigate the performance of our approach on applications from open pit mine production scheduling and water distribution network design and on various benchmarks sets. The results show that SCIP has become a competitive solver for MINLPs.