[pt] Nesta tese, abordamos o escalonamento de profissionais de saúde para propor um uso mais eficiente da capacidade existente e fornecer acesso oportuno em diferentes serviços de saúde. Apresentamos um conjunto de problemas relacionados à programação de equipes de saúde. O primeiro problema procura reduzir o tempo de porta-médico em uma unidade de pronto atendimento; o segundo problema visa reduzir o tempo de espera total de tratamento também em uma unidade de pronto atendimento; o terceiro problema visa fornecer acesso oportuno à consulta clínica e à cirurgia em uma unidade cirúrgica especializada. Foram propostos e resolvidos modelos de programação estocástica de dois estágios que procuram representar com precisão as características particulares inerentes a cada problema. Um aspecto importante em problemas de saúde é o grande número de incertezas envolvidas nos processos. A incorporação da incerteza aumenta a complexidade do problema e, portanto, torna-se impossível computacionalmente considerar todos os cenários possíveis. Essa dificuldade é contornada usando a Aproximação por Média Amostral (SAA) para representar a incerteza na demanda. Modelo de simulação de eventos discretos (DES) é usado para representar os problemas. Por fim, as soluções foram aplicadas a estudos de caso reais, mostrando que os modelos propostos são adaptáveis a diferentes prestadores de serviços de saúde. Ao longo da tese, resolvemos com eficiência os modelos utilizando casos reais de hospitais no Brasil e nos EUA. / [en] In this thesis, we approach the problem of healthcare staff scheduling to propose a more efficient use of existing capacity to provide timely access in different health services. We present a set of problems related to healthcare staff scheduling. The first problem seeks to reduce the door-to-doctor time in an Emergency Department; the second problem aims to reduce the waiting time of the overall treatment also in an Emergency Department; the third problem aims to provide timely access to both clinic and surgery in a specialized surgical unit. We formulate and solve two-stage stochastic programming models that seek to accurately represent the particular features that are inherent of each problem. An important aspect in healthcare problems is a large number of uncertainties involved in the processes. The incorporation of the uncertainty increases the complexity of the problem, and it, therefore, becomes computationally infeasible to consider all of the possible scenarios. We circumvent this difficulty by relying on Sample Average Approximation (SAA) to address the demand uncertainty. We also use a discrete-event simulation (DES) model to represent the problems. Finally, we apply the framework to real case studies showing that the proposed models are adaptable to different healthcare providers. Throughout the thesis, we efficiently solve the models using real cases of Brazil and USA hospitals.

Die Dissertationsschrift thematisiert die Frage nach den Kosten und Nutzen einer Diversifikationsstrategie im europäischen Erdgasmarkt und gliedert sich in neun Kapitel. In einer Vorbetrachtung beschreiben die Kapitel eins bis vier die Ausganglage mit Blick auf Angebots- und Nachfragestrukturen sowie der Gasinfrastruktur. Unsicherheiten in Bezug auf die Entwicklung der Nachfrage, Importverfügbarkeit und Preisniveaus werden diskutiert. In einem analytischen Rahmen wird das Thema Diversifikation in den Kontext der Energiesicherheit eingeordnet. Die Kapitel fünf bis sieben befassen sich mit der Beschreibung und der Analyse des europäischen Gasmarkts. Dafür wird ein lineares Modell, GAMAMOD-EU, entwickelt, welches als stochastische Optimierung den Ausbau der Erdgasinfrastruktur unter Einbezug von drei Unsicherheitsdimensionen in den Jahren 2030 und 2045 abbildet. Zusätzlich werden drei Diversifikationsstrategien in Hinblick auf Infrastrukturentwicklung und Versorgungssicherheit analysiert. In einer Erweiterung wird der Import Grüner Gase in die Betrachtung einbezogen. Kapitel acht stellt das deutsche Gasnetzmodell GAMAMOD-DE mit einer Fallstudie vor, die die Versorgungslage im kalten Winter 2012 nachmodelliert. Im abschließenden Kapitel neun werden die zu Beginn aufgeworfenen Forschungsfragen beantwortet, politische Handlungsempfehlungen gegeben und der weitere Forschungsbedarf skizziert.:Table of Contents List of Figures List of Tables Abbreviations Country Codes Nomenclature: GAMAMOD-EU Nomenclature: GAMAMOD-DE 1 Introduction 2 Uncertainties in Gas Markets 3 Diversification in Gas Markets to Ensure Security of Supply 4 Natural Gas Infrastructure 5 The European Natural Gas Market Model (GAMAMOD-EU) 6 Results on Security of Supply in the European Gas Market 7 Impact of Green Gas Imports on Infrastructure Investments 8 The German Natural Gas Market Model (GAMAMOD-DE) 9 Conclusion and Outlook Laws and Communication Papers References Appendix / The dissertation addresses the question of the costs and benefits of a diversification strategy in the European natural gas market and is divided into nine chapters. In a preliminary analysis, chapters one to four describe the initial situation with regard to supply and demand structures as well as the gas infrastructure. Uncertainties regarding the development of demand, import availability and price levels are discussed. In an analytical framework, the topic of diversification is placed in the context of energy security. Chapters five to seven deal with the description and analysis of the European gas market. For this purpose, a linear model, GAMAMOD-EU, is developed, which maps the expansion of the natural gas infrastructure as a stochastic optimisation, taking into account three uncertainty dimensions in the years 2030 and 2045. In addition, three diversification strategies are analysed with regard to infrastructure development and security of supply. In an extension, the import of green gases is included in the analysis. Chapter eight presents the German gas grid model GAMAMOD-DE with a case study, which models the supply situation in the cold winter of 2012. In the concluding chapter nine, the research questions raised at the beginning are answered, political recommendations for action are given and the need for further research is outlined.:Table of Contents List of Figures List of Tables Abbreviations Country Codes Nomenclature: GAMAMOD-EU Nomenclature: GAMAMOD-DE 1 Introduction 2 Uncertainties in Gas Markets 3 Diversification in Gas Markets to Ensure Security of Supply 4 Natural Gas Infrastructure 5 The European Natural Gas Market Model (GAMAMOD-EU) 6 Results on Security of Supply in the European Gas Market 7 Impact of Green Gas Imports on Infrastructure Investments 8 The German Natural Gas Market Model (GAMAMOD-DE) 9 Conclusion and Outlook Laws and Communication Papers References Appendix

Stochastic programming is an optimization technique that incorporates random variables as parameters. Because it better reflects the uncertain real world than its traditional deterministic counterpart, stochastic programming has drawn increasingly more attention among decision-makers, and its applications span many fields including financial engineering, health care, communication systems, and supply chain management. On the flip side, stochastic programs are usually very difficult to solve, which is further compounded by the fact that in many of the aforementioned applications, we also have discrete decisions, thereby rendering these problems even more challenging. In this dissertation, we study the class of two-stage stochastic mixed-integer programs (SMIP), which, as its name suggests, lies at the confluence of two formidable classes of problems. We design a novel algorithm for this class of problems, and also explore specialized approaches for two related real-world applications. Although a number of algorithms have been developed to solve two-stage SMIPs, most of them deal with problems containing purely integer or continuous variables in either or both of the two stages, and frequently require the technology and/or recourse matrices to be deterministic. As a ground-breaking effort, in this work, we address the challenging class of two-stage SMIPs that involve 0-1 mixed-integer variables in both stages. The only earlier work on solving such problems (Carøe and Schultz (1999)) requires the optimization of several non-smooth Lagrangian dual problems using subgradient methods in the bounding process, which turns out to be computationally very expensive. We begin with proposing a decomposition-based branch-and-bound (DBAB) algorithm for solving two-stage stochastic programs having 0-1 mixed-integer variables in both stages. Since the second-stage problems contain binary variables, their value functions are in general nonconvex and discontinuous; hence, the classical Benders' decomposition approach (or the L-shaped method) for solving two-stage stochastic programs, which requires convex subproblem value functions, cannot be directly applied. This motivates us to relax the second-stage problems and accompany this relaxation with a convexification process. To make this process computationally efficient, we propose to construct a certain partial convex hull representation of the two-stage solution space, using the relaxed second-stage constraints and the restrictions confining the first-stage variables to lie within some hyperrectangle. This partial convex hull is sequentially generated using a convexification scheme, such as the Reformulation-Linearization Technique (RLT), which yields valid inequalities that are functions of the first-stage variables and, of noteworthy importance, are reusable in the subsequent subproblems by updating the values of the first-stage variables. Meanwhile, since the first stage contains continuous variables, whenever we tentatively fix these variables at some given feasible values, the resulting constraints may not be facial with respect to the associated bounding constraints that are used to construct the partial convex hull. As a result, the constructed Benders' subproblems define lower bounds for the second-stage value functions, and likewise, the resulting Benders' master problem provides a lower bound for the original stochastic program defined over the same hyperrectangle. Another difficulty resulting from continuous first-stage variables is that when the given first-stage solution is not extremal with respect to its bounds, the second-stage solution obtained for a Benders' subproblem defined with respect to a partial convex hull representation in the two-stage space may not satisfy the model's binary restrictions. We thus need to be able to detect whether or not a Benders' subproblem is solved by a given fractional second-stage solution. We design a novel procedure to check this situation in the overall algorithmic scheme. A key property established, which ensures global convergence, is that these lower bounds become exact if the given first-stage solution is a vertex of the defining hyperrectangle, or if the second-stage solution satisfies the binary restrictions. Based on these algorithmic constructs, we design a branch-and-bound procedure where the branching process performs a hyperrectangular partitioning of the projected space of the first-stage variables, and lower bounds for the nodal problems are computed by applying the proposed modified Benders' decomposition method. We prove that, when using the least-lower-bound node-selection rule, this algorithm converges to a global optimal solution. We also show that the derived RLT cuts are not only reusable in subsequent Benders iterations at the same node, but are also inheritable by the subproblems of the children nodes. Likewise, the Benders' cuts derived for a given sub-hyperrectangle can also be inherited by the lower bounding master programs solved for its children nodes. Using these cut inheritance properties results in significant savings in the overall computational effort. Some numerical examples and computational results are presented to demonstrate the efficacy of this approach. The sizes of the deterministic equivalent of our test problems range from having 386 continuous variables, 386 binary variables, and 386 constraints, up to 1795 continuous variables, 1539 binary variables, and 1028 constraints. The results reveal an average savings in computational effort by a factor of 9.5 in comparison with using a commercial mixed-integer programming package (CPLEX 8.1) on a deterministic equivalent formulation. We then explore an important application of SMIP to enhance the traditional airline fleet assignment models (FAM). Given a flight schedule network, the fleet assignment problem solved by airline companies is concerned with assigning aircraft to flight legs in order to maximize profit with respect to captured path- or itinerary-based demand. Because certain related crew scheduling regulations require early information regarding the type of aircraft serving each flight leg, the current practice adopted by airlines is to solve the fleet assignment problem using estimated demand data 10-12 weeks in advance of departure. Given the level of uncertainty, deterministic models at this early stage are inadequate to obtain a good match of aircraft capacity with passenger demands, and revisions to the initial fleet assignment become naturally pertinent when the observed demand differs considerably from the assigned aircraft capacities. From this viewpoint, the initial decision should embrace various market scenarios so that it incorporates a sufficient look-ahead feature and provides sufficient flexibility for the subsequent re-fleeting processes to accommodate the inevitable demand fluctuations. With this motivation, we propose a two-stage stochastic programming approach in which the first stage is concerned with the initial fleet assignment decisions and, unlike the traditional deterministic methodology, focuses on making only a family-level assignment to each flight leg. The second stage subsequently performs the detailed assignments of fleet types within the allotted family to each leg under each of the multiple potential scenarios that address corresponding path- or itinerary-based demands. In this fashion, the initial decision of what aircraft family should serve each flight leg accomplishes the purpose of facilitating the necessary crew scheduling decisions, while judiciously examining the outcome of future re-fleeting actions based on different possible demand scenarios. Hence, when the actual re-fleeting process is enacted several weeks later, this anticipatory initial family-level assignment will hopefully provide an improved overall fleet type re-allocation that better matches demand. This two-stage stochastic model is complemented with a secondary model that performs adjustments within each family, if necessary, to provide a consistent fleet type-assignment information for accompanying decision processes, such as yield management. We also propose several enhanced fleet assignment models, including a robust optimization model that controls decision variation among scenarios and a stochastic programming model that considers the recapture effect of spilled demand. In addition to the above modeling concepts and framework, we also contribute in developing effective solution approaches for the proposed model, which is a large-scale two-stage stochastic 0-1 mixed-integer program. Because the most pertinent information needed from the initial fleet assignment is at the family level, and the type-level assignment is subject to change at the re-fleeting stage according to future demand realizations, our solution approach focuses on assigning aircraft families to the different legs in the flight network at the first stage, while finding relaxed second-stage solutions under different demand scenarios. Based on a polyhedral study of a subsystem extracted from the original model, we derive certain higher-dimensional convex hull as well as partial convex hull representations for this subsystem. Accordingly, we propose two variants for the primary model, both of which relax the binary restrictions on the second-stage variables, but where the second variant then also accommodates the partial convex hull representations, yielding a tighter, albeit larger, relaxation. For each variant, we design a suitable solution approach predicated on Benders' decomposition methodology. Using certain realistic large-scale flight network test problems having 900 flight legs and 1,814 paths, as obtained from United Airlines, the proposed stochastic modeling approach was demonstrated to increase daily expected profits by about 3% (which translates to about $160 million per year) in comparison with the traditional deterministic model in present usage, which considers only the expected demand. Only 1.6% of the second-stage binary variables turn out to be fractional in the first variant, and this number is further reduced to 1.2% by using the tighter variant. Furthermore, when attempting to solve the deterministic equivalent formulation for these two variants using a commercial mixed-integer programming package (CPLEX 8.1), both the corresponding runs were terminated after reaching a 25-hour cpu time limit. At termination, the software was still processing the initial LP relaxation at the root node for each of these runs, and no feasible basis was found. Using the proposed algorithms, on the other hand, the solution times were significantly reduced to 5 and 19 hours for the two variants, respectively. Considering that the fleet assignment models are solved around three months in advance of departure, this solution time is well acceptable at this early planning stage, and the improved quality in the solution produced by considering the stochasticity in the system is indeed highly desirable. Finally, we address another practical workforce planning problem encountered by a global financial firm that seeks to manage multi-category workforce for functional areas located at different service centers, each having office-space and recruitment-capacity constraints. The workforce demand fluctuates over time due to market uncertainty and dynamic project requirements. To hedge against the demand fluctuations and the inherent uncertainty, we propose a two-stage stochastic programming model where the first stage makes personnel recruiting and allocation decisions, while the second stage, based on the given personnel decision and realized workforce demand, decides on the project implementation assignment. The second stage of the proposed model contains binary variables that are used to compute and also limit the number of changes to the original plan. Since these variables are concerned with only one quality aspect of the resulting workforce plan and do not affect feasibility issues, we replace these binary variables with certain conservative policies regarding workforce assignment change restrictions in order to obtain more manageable subproblems that contain purely continuous variables. Numerical experiments reveal that the stochastic programming approach results in significantly fewer alterations to the original workforce plan. When using a commercial linear programming package CPLEX 9.0 to solve the deterministic equivalent form directly, except for a few small-sized problems, this software failed to produce solutions due to memory limitations, while the proposed Benders' decomposition-based solution approach consistently solved all the practical-sized test problems with reasonable effort. To summarize, this dissertation provides a significant advancement in the algorithmic development for solving two-stage stochastic mixed-integer programs having 0-1 mixed-integer variables in both stages, as well as in its application to two important contemporary real-world applications. The framework for the proposed solution approaches is to formulate tighter relaxations via partial convex hull representations and to exploit the resulting structure using suitable decomposition methods. As decision robustness is becoming increasingly relevant from an economic viewpoint, and as computer technological advances provide decision-makers the ability to explore a wide variety of scenarios, we hope that the proposed algorithms will have a notable positive impact on solving stochastic mixed-integer programs. In particular, the proposed stochastic programming airline fleet assignment and the workforce planning approaches studied herein are well-poised to enhance the profitability and robustness of decisions made in the related industries, and we hope that similar improvements are adapted by more industries where decisions need to be made in the light of data that is shrouded by uncertainty. / Ph. D.

[pt] O presente trabalho tem como foco o estudo do Sistema Petrobras, no que tange o planejamento estratégico dos investimentos da Companhia, sob a ótica da cadeia integrada do petróleo. A partir de um dos modelos matemáticos mais utilizados (e há mais tempo) na empresa, diversas decisões estratégicas de suma importância são suportadas, de modo a maximizar seu resultado operacional ao longo de um horizonte de tempo da ordem de 10 (dez) anos. Com embasamento na literatura atual, evoluções são propostas e testadas no modelo matemático. Primeiramente são introduzidas técnicas de programação estocástica em dois estágios, onde as decisões de investimento são representadas por variáveis de primeiro estágio; e a operação de todo o sistema – desde o refino até a comercialização do petróleo e derivados, passando por toda a questão logística – passa a fazer parte do segundo estágio, após a realização / revelação dos parâmetros estocásticos. Em um segundo passo, técnicas de decomposição são aplicadas para contornar eventuais limitações geradas pelo grande porte atingido pelo modelo, que cresce proporcionalmente ao número de cenários envolvidos na otimização. Os resultados mostram que o modelo estocástico começa a esbarrar nestas limitações a partir da resolução de problemas com mais de 30 cenários. Por outro lado, apesar do tempo computacional consideravelmente maior, o modelo decomposto chegou a resolver até 80 cenários, nos testes realizados. / [en] This work focuses on the study of Petrobras, regarding the strategic planning of the Company s investments, from an integrated oil supply chain perspective. From one of the most widely used mathematical models in the Company, several strategic decisions of great importance are supported, so as to maximize its operating result over a time horizon of approximately 10 (ten) years. Based in current literature, developments are proposed and tested in the mathematical model. First, two-stage stochastic programming techniques are introduced, where investment decisions are represented by first-stage variables; and system s operation – from oil refining and sales to the entire logistics issue – by second-stage variables, after realization of the stochastic parameters. In a second step, decomposition techniques are applied to circumvent any large scale limitations. The results show that the stochastic model starts to reach these limitations in problems with 30 scenarios or more. On the other hand, despite the considerably greater computational time, the decomposed model was able to solve up to 80-scenarios problems, during the tests.

Ce projet de recherche a été réalisé avec la collaboration de FPInnovations. Une part des travaux concernant le problème de récolte chilien a été effectuée à l'Instituto Sistemas Complejos de Ingeniería (ISCI) à Santiago (Chili). / La planification de la récolte forestière comporte différents niveaux de planification selon l'horizon de temps du problème et la nature des décisions à prendre. Dans un premier temps, nous nous intéressons à un problème de planification annuelle de la récolte, à mi-chemin entre la planification tactique et opérationnelle. Ce problème appliqué à l'exploitation forestière au Québec, naît d'un besoin de l'industrie québécoise d'un outil pour la planification annuelle intégrée qui fournit aux équipes de récolte leur calendrier. L'intégration consiste à déterminer les affectations des équipes aux blocs en fonction des besoins des usines, et qui respectent les contraintes de transport, de gestion des stocks, et bien entendu les conditions d'exploitation en forêt. Plusieurs modèles de types MIP ont été formulés, des approches de résolution adaptées à la structure de chacun des modèles ont été développées. L'approche par horizon roulant est celle dont les résultats surpassent les deux autres et surtout, améliorent de façon significative les plans usuellement suivis, notamment en réduisant les volumes non livrés aux usines de moitié, ou encore en divisant entre 2 et 6 fois les volumes en stock quand la demande diminue. De plus, le développement d'une interface pour systématiser le processus de résolution et élargir le nombre d'utilisateurs, est la seconde contribution de la thèse. Cette étape du projet correspond à un transfert de technologie de l'université vers l'industrie. Le second problème de planification se situe au Chili, est une planification tactique de la récolte dirigée par les prix et demandes en produits finis, ces derniers étant considérés comme des paramètres aléatoires. Le problème stochastique formulé est résolu suivant une méthode de décomposition par scénarios dont le nombre varie entre 10 et 100. Pour chaque scénario, la solution déterministe, lorsqu'elle est réalisable, est comparée avec celle issue de la résolution du problème stochastique. La solution déterministe n'est réalisable que pour une dizaine de scénarios parmi 100, et les pertes encourues sont en moyenne de 9%. / Harvest planning has different levels according to the time horizon of the problem and the nature of the decisions to be taken. Initially, we are interested in an annual harvest scheduling problem, halfway between tactical and operational planning. This problem applied in Qu\'ebec, is motivated by a need from the industry for an integrated tool that provides annual schedules to harvest teams. The integration is to determine demand driven assignments of teams to cutblocks and to manage transportation and inventory accordingly. Several MIP models have been formulated, and three solution approaches have been developed according to the structure of each model. The rolling horizon approach performs better than the other two, by improving significantly from the traditional harvest plan, especially by reducing by half non delivered volumes or by dividing between 2 and 6 times volumes in storage when demands decrease. Another contribution of the thesis is the creation of an interface to systematize solution process and to allow other users. This is the object of a transfer project between academics and industry. The second problem is a Chilean tactical harvest planning. Harvesting decisions are driven by stochastic demands and prices of final products. The stochastic problem is solved using a heuristic based on a scenario decomposition technique. The number of scenarios considered is between 10 and 100 scenarios. For each scenario, when the deterministic solution is feasible, it is compared with the stochastic solution for the current scenario. The deterministic solution is only feasible for 10% of the scenarios, and induces losses of 9% in average.

<p>U disertaciji je razmatran problem stohastičkog programiranja s ograničenjima tipa jednakosti, odnosno problem minimizacije s ograničenjima koja su u obliku matematičkog očekivanja. Za re&scaron;avanje posmatranog problema kreirana su dva iterativna postupka u kojima se u svakoj iteraciji računa s uzoračkim očekivanjem kao aproksimacijom matematičkog očekivanja. Oba postupka koriste prednosti postupaka s promenljivom veličinom uzorka zasnovanih na adaptivnom ažuriranju veličine uzorka. To znači da se veličina uzorka određuje na osnovu informacija u tekućoj iteraciji. Konkretno, tekuće informacije o preciznosti aproksimacije očekivanja i tačnosti aproksimacije re&scaron;enja problema defini&scaron;u veličinu uzorka za narednu iteraciju. Oba iterativna postupka su zasnovana na linijskom pretraživanju, a kako je u pitanju problem s ograničenjima, i na kvadratnom kaznenom postupku prilagođenom stohastičkom okruženju. Postupci su zasnovani na istim idejama, ali s različitim pristupom.<br />Po prvom pristupu postupak je kreiran za re&scaron;avanje SAA reformulacije problema stohastičkog programiranja, dakle za re&scaron;avanje aproksimacije originalnog problema. To znači da je uzorak definisan pre iterativnog postupka, pa je analiza konvergencije algoritma deterministička. Pokazano je da se, pod standardnim pretpostavkama, navedenim algoritmom dobija podniz iteracija čija je tačka nagomilavanja KKT tačka SAA reformulacije.<br />Po drugom pristupu je formiran algoritam za re&scaron;avanje samog problema<br />stohastičkog programiranja, te je analiza konvergencije stohastička. Predstavljenim algoritmom se generi&scaron;e podniz iteracija čija je tačka nagomilavanja, pod standardnim pretpostavkama za stohastičku optimizaciju, skoro sigurno<br />KKT tačka originalnog problema.<br />Predloženi algoritmi su implementirani na istim test problemima. Rezultati numeričkog testiranja prikazuju njihovu efikasnost u re&scaron;avanju posmatranih problema u poređenju s postupcima u kojima je ažuriranje veličine uzorka<br />zasnovano na unapred definisanoj &scaron;emi. Za meru efikasnosti je upotrebljen<br />broj izračunavanja funkcija. Dakle, na osnovu rezultata dobijenih na skupu<br />testiranih problema može se zaključiti da se adaptivnim ažuriranjem veličine<br />uzorka može u&scaron;tedeti u broju evaluacija funkcija kada su u pitanju i problemi s<br />ograničenjima.<br />Kako je posmatrani problem deterministički, a formulisani postupci su stohastički, prva tri poglavlja disertacije sadrže osnovne pojmove determinističke<br />i stohastiˇcke optimizacije, ali i kratak pregled definicija i teorema iz drugih<br />oblasti potrebnih za lak&scaron;e praćenje analize originalnih rezultata. Nastavak disertacije čini prikaz formiranih algoritama, analiza njihove konvergencije i numerička implementacija.<br />&nbsp;</p> / <p>Stochastic programming problem with equality constraints is considered within thesis. More precisely, the problem is minimization problem with constraints in the form of mathematical expectation. We proposed two iterative methods for solving considered problem. Both procedures, in each iteration, use a sample average function instead of the mathematical expectation function, and employ the advantages of the variable sample size method based on adaptive updating the sample size. That means, the sample size is determined at every iteration using information from the current iteration. Concretely, the current precision of the approximation of expectation and the quality of the approximation of solution determine the sample size for the next iteration. Both iterative procedures are based on the line search technique as well as on the quadratic penalty method adapted to stochastic environment, since the considered problem has constraints. Procedures relies on same ideas, but the approach is different.<br />By first approach, the algorithm is created for solving an SAA reformulation of the stochastic programming problem, i.e., for solving the approximation of the original problem. That means the sample size is determined before the iterative procedure, so the convergence analyses is deterministic. We show that, under the standard assumptions, the proposed algorithm generates a subsequence which accumulation point is the KKT point of the SAA problem. Algorithm formed by the second approach is for solving the stochastic programming problem, and therefore the convergence analyses is stochastic. It generates a subsequence with&nbsp; accumulation point that is almost surely the KKT point of the original problem, under the standard assumptions for stochastic optimization.for sample size. The number of function evaluations is used as measure of efficiency. Results of the set of tested problems suggest that it is possible to make smaller number of function evaluations by adaptive sample size scheduling in the case of constrained problems, too.<br />Since the considered problem is deterministic, but the formed procedures are stochastic, the first three chapters of thesis contain basic notations of deterministic and stochastic optimization, as well as a short sight of definitions and theorems from another fields necessary for easier tracking the original results analysis. The rest of thesis consists of the presented algorithms, their convergence analysis and numerical implementation.</p>

Orientador: José Roberto Sanches Mantovani / Resumo: Neste trabalho propõem-se formulações matemáticas e metodologias para resolver o problema de planejamento da expansão e operação de sistemas de distribuição de energia elétrica de longo prazo com instalação de geração distribuída despachável, renovável e dispositivos armazenadores de energia, considerando as incertezas nos parâmetros e variáveis envolvidas no comportamento do sistema. No modelo de otimização desenvolvido considera- se uma formulação com espaço de busca convexo como um problema de programação cônica inteira de segunda ordem. Como primeira metodologia de solução para o modelo matemático proposto, usam-se solvers de otimização comerciais através de linguagem de programação matemática. Em segundo lugar é proposta a técnica de otimização meta-heurística VND combinada com um solver de otimização para resolver o modelo de otimização desenvolvido. Os algoritmos e modelos matemáticos de otimização usados para resolver o planejamento de sistemas de distribuição são implementados em AMPL e testados em sistemas presentes na literatura. Finalmente são comparadas as metodologias segundo a solução obtida e desempenho em tempo computacional. / Abstract: This work proposes mathematical formulations and methodologies to solve the long-term electric power distribution system operation and expansion planning with distributed renewable energy sources and energy storage devices, considering the uncertainties in the involved parameters and variables in the system behavior. In the developed optimization model, a convex formulation is considered as integer second-order conic programming problem. The first solution methodology for the proposed mathematical model, the commercial optimization solvers that uses mathematical modelling language is used. In the second way, the VND meta-heuristic optimization technique is proposed combined with the optimization solver to analyze the obtained solutions of the search through optimal neighborhoods. The mathematical optimization model and the proposed algorithm used to solver the planning of distribution systems are implemented in AMPL and tested in literature’s systems. Finally, the methodologies according to the obtained solution and computational time performance are compared. / Doutor

資產配置乃是將資金分散投資到主要的資產類別中，諸如股票、債券、現金等。傳統的均數/變異數方法在資產配置上早已被廣泛的運用。但是，現今的金融情勢多變，多期配置的需求提高，傳統均數/變異數方法只處理單一期間的資產配置，且反應未來的能力不佳，顯然已經不適用。 本論文提供一種多期動態的資產配置，可以改良過去單點估計值的缺點，同時能夠將未來情境納入考量，使多期資產配置更富策略性。並實證在兩期的情況下，期中調整資產組合與不調整的差異性。從而瞭解持續的動態規劃，方能提升資產配置的效率性。 / Asset allocation is the process of dividing an investment fund among major asset classes such as equities, bonds, cash, etc. Traditional mean-variance portfolio selection is widely used for asset allocation. However, as time goes by, the financial condition changes rapidly. The method of mean-variance analysis has some limitations. It not only can’t deal with multiperiod asset allocation, but also cannot reflect future economic circumstances, especially for long-term investments. This research tries to use the method of multi-stage dynamic programming for asset allocation. This method can improve the pits of single estimate in using mean-variance analysis, and take future scenarios into account so that the model will become more useful in practice. The two-period empirical results have shown that using continuous dynamic programming to build strategic asset allocation decision can improve the efficiency of asset allocation.

<p>The Swedish National Debt Office (SNDO) is the Swedish Government’s financial administration. It has several tasks and the main one is to manage the central government’s debt in a way that minimizes the cost with due regard to risk. The debt management problem is to choose currency composition and maturity profile - a problem made difficult because of the many stochastic factors involved. </p><p>The SNDO has created a simulation model to quantitatively analyze different aspects of this problem by evaluating a set of static strategies in a great number of simulated futures. This approach has a number of drawbacks, which might be handled by using a financial optimization approach based on Stochastic Programming. </p><p>The objective of this master’s thesis is thus to apply financial optimization on the Swedish government’s strategic debt management problem, using the SNDO’s simulation model to generate scenarios, and to evaluate this approach against a set of static strategies in fictitious future macroeconomic developments. </p><p>In this report we describe how the SNDO’s simulation model is used along with a clustering algorithm to form future scenarios, which are then used by an optimization model to find an optimal decision regarding the debt management problem. </p><p>Results of the evaluations show that our optimization approach is expected to have a lower average annual real cost, but with somewhat higher risk, than a set of static comparison strategies in a simulated future. These evaluation results are based on a risk preference set by ourselves, since the government has not expressed its risk preference quantitatively. We also conclude that financial optimization is applicable on the government debt management problem, although some work remains before the method can be incorporated into the strategic work of the SNDO.</p>

<p>This thesis grew out of a problem encountered by a subsidiary of a Swedish multinational industrial corporation. This subsidiary is responsible for the corporation’s customer financing activities. In the thesis, we refer to these entities as the Division and the Corporation. The Division needed to find a new approach to finance its customer loan portfolio. Risk control and return maximization were important aspects of this need. The objective of this thesis is to devise and implement a method that allows the Division to make optimal funding decisions, given a certain risk limit. </p><p>We propose a funding approach based on stochastic programming. Our approach allows the Division’s portfolio manager to minimize the funding costs while hedging against market risk. We employ principal component analysis and Monte Carlo simulation to develop a multicurrency scenario generation model for interest and exchange rates. Market rate scenarios are used as input to three different optimization models. Each of the optimization models presents the optimal funding decision as positions in a unique set of financial instruments. By choosing between the optimization models, the portfolio manager can decide which financial instruments he wants to use to fund the loan portfolio. </p><p>To validate our models, we perform empirical tests on historical market data. Our results show that our optimization models have the potential to deliver sound and profitable funding decisions. In particular, we conclude that the utilization of one of our optimization models would have resulted in an increase in the Division’s net income over the past 3.5 years.</p>