This thesis deals with multi-stage stochastic programming in the context of random process representation. Basic structure for random process is a scenario tree. The thesis introduces general and stage-independent scenario tree and their properties. Scenario trees can be also combined with Markov chains which describe the state of the system and determine which scenario tree should be used. Another structure which enables reduce the complexity of the problem is a scenario lattice. Scenario generation is performed using moment method. Scenario trees are used for representation of random returns as the input to the investment problem.

This thesis deals with multi-stage stochastic programming in the context of random process representation. Basic structure for random process is a scenario tree. The thesis introduces general and stage-independent scenario tree and their properties. Scenario trees combined with Markov chains are also introduced. Markov chains states determine if there is a crisis period or not. Information about historical number of crises helps us to construct a scenario lattice. Scenario generation is performed using moment method. Scenario trees are used as an input to the investment problem.

Since the deregulation of the Nordic electricity market in 1996, electricity has become one of the most traded commodities in the Nordic region. The electricity price is characterized by large fluctuations as the supply and demand of electricity are seasonally dependent. The main interest of the hydro power producers is to assure that they can sell their hydro power at an attractive rate over time. This means that there is a demand for hedging against these fluctuations which in turn creates trading opportunities for third party actors that offer solutions between consumers and producers. Telge Krafthandel is one of these actors interested in predicting the future supply of hydro power, and consequently the resulting price of electricity. Several existing models employ the assumption of perfect foresight regarding the weather in the future. In this thesis, the authors develop new models for hydro power optimization that take hydrological uncertainty into account by implementing a variation of multi-stage optimization in order to maximize the income of the hydro power producers. The optimization is performed with respect to prices of financial derivatives on electricity. This gives insights into the expected supply of hydro power in the future which in turn can be used as an indicator of the price of electricity. The thesis also discusses, among other things, different methods for modeling stochastic inflow to the reservoirs and scenario construction. This practice will result in different methods that are suitable for various key players in the industry. / Sedan avregleringen av den Nordiska elmarknaden år 1996 har el blivit en av de mest handlade råvarorna i Norden. Elpriset karaktäriseras av stora svängningar eftersom utbudet och efterfrågan på el är säsongsberoende. Huvudintresset för vattenkraftsproducenter är att säkerställa att de kan sälja sin vattenkraft till ett attraktivt pris över tid. Detta innebär att det finns en efterfrågan för skydd mot dessa variationer, vilket i sin tur skapar affärsmöjligheter för tredjepartsaktörer som erbjuder lösningar mellan konsumenter och producenter. Telge Krafthandel är en av dessa aktörer och är därmed intresserad av att förutsäga det framtida utbudet på vattenkraft, och det resulterande elpriset. Flera befintliga modeller använder antagandet om perfekt förutseende när det gäller vädret i framtiden. I denna rapport utvecklar författarna nya modeller för vattenkraftsoptimering, som tar hänsyn till hydrologisk osäkerhet genom att implementera en variant av flerstegsoptimering för att maximera intäkterna för vattenkraftsproducenter. Optimeringen utförs med hänsyn till priserna på elderivat. Detta ger insikter i den förväntade tillgången på vattenkraft i framtiden, vilket i sin tur kan användas som en indikator på elpriset. I rapporten diskuteras också, bland annat, olika metoder för att modellera stokastiskt inflöde till vattenmagasinen och scenariokonstruktion. Detta kommer att leda till flera metoder som är lämpliga för olika aktörer i branschen.

This thesis deals with stochastic location routing problem. Multiple stochas- tic and deterministic models are formulated and it is discussed that it is difficult to solve these problems via exact integer programming methods. It is necessary to develop heuristic methods to find a solution of these problems. Multiple ver- sions of these problems are formulated and their properties and possibilities how to solve them are discussed. Therefore, the brand new Blockchain metaheuristic is developed and later used for solving stochastic location routing problem ap- plied on a waste collection problem. As a part of Blockchain metaheuristic we develop the new application of Greedy algorihtm that is used for finding initial solution. The quality of the heuristic algorithm developed by us is presented in a numerical study. 1

Forest fires cause a significant amount of damage and destruction each year. Optimally dispatching resources reduces the amount of damage a forest fire can cause. Models predict the fire spread to provide the data required to optimally dispatch resources. However, the models are only as accurate as the data used to build them. Satellites are one valuable tool in the collection of data for the forest fire models. Satellites provide data on the types of vegetation, the wind speed and direction, the soil moisture content, etc. The current operating paradigm is to passively collect data when possible. However, images from directly overhead provide better resolution and are easier to process. Maneuvering a constellation of satellites to fly directly over the forest fire provides higher quality data than is achieved with the current operating paradigm. Before launch, the location of the forest fire is unknown. Therefore, it is impossible to optimize the initial orbits for the satellites. Instead, the expected cost of maneuvering to observe the forest fire determines the optimal initial orbits. A two-stage stochastic programming approach is well suited for this class of problem where initial decisions are made with an uncertain future and then subsequent decisions are made once a scenario is realized. A repeat ground track orbit provides a non-maneuvering, natural solution providing a daily flyover of the forest fire. However, additional maneuvers provide a second daily flyover of the forest fire. The additional maneuvering comes at a significant cost in terms of additional fuel, but provides more data collection opportunities. After data are collected, ground stations receive the data for processing. Optimally selecting the ground station locations reduce the number of built ground stations and reduces the data fusion issues. However, the location of the forest fire alters the optimal ground station sites. A two-stage stochastic programming approach optimizes the selection of ground stations to maximize the expected amount of data downloaded from a satellite. The approaches of selecting initial orbits and ground station locations including uncertainty will provide a robust system to reduce the amount of damage caused by forest fires.

Dynamic OD estimators based on traffic measurements inevitably encounter the indeterminateness problem on the posterior OD flows as such systems structurally have more unknowns than constraints. To resolve this problem and take advantage of the emerging urban mobility data, the paper proposes a dynamic OD estimator based on location-based social networking (LBSN) data, leveraging the two-stage stochastic programming framework, under the assumption that similar check-in patterns are generated by the same OD pattern. The search space of the OD flows will be limited by integrating a batch of realizations/scenarios of the second-stage problem state (i.e. check-in pattern) in the model. The two-stage stochastic programming model decomposes in a master problem and a set of subproblems (one per scenario) via the Benders decomposition algorithm, which will be tackled alternately. The preliminary results from experiments conducted with the Foursquare data of Tokyo, Japan, show that the proposed OD estimator can effectively recurrent the check-in patterns and result in a good posterior OD estimate.

<div>Stochastic programs are standard models for decision-making under uncertainty and have been extensively studied in the operations research literature. In general, stochastic programming involves minimizing an expected cost function, where the expectation is with respect to fully specified stochastic models that quantify the aleatoric or `inherent' uncertainty in the decision-making problem. In practice, however, the stochastic models are unknown but can be estimated from data, introducing an additional epistemic uncertainty into the decision-making problem. The Bayesian framework provides a coherent way to quantify the epistemic uncertainty through the posterior distribution by combining prior beliefs of the decision-makers with the observed data. Bayesian methods have been used for data-driven decision-making in various applications such as inventory management, portfolio design, machine learning, optimal scheduling, and staffing, etc.</div><div> </div><div>Bayesian methods are challenging to implement, mainly due to the fact that the posterior is computationally intractable, necessitating the computation of approximate posteriors. Broadly speaking, there are two methods in the literature implementing approximate posterior inference. First are sampling-based methods such as Markov Chain Monte Carlo. Sampling-based methods are theoretically well understood, but they suffer from various issues like high variance, poor scalability to high-dimensional problems, and have complex diagnostics. Consequently, we propose to use optimization-based methods collectively known as variational inference (VI) that use information projections to compute an approximation to the posterior. Empirical studies have shown that VI methods are computationally faster and easily scalable to higher-dimensional problems and large datasets. However, the theoretical guarantees of these methods are not well understood. Moreover, VI methods are empirically and theoretically less explored in the decision-theoretic setting.</div><div><br></div><div> In this thesis, we first propose a novel VI framework for risk-sensitive data-driven decision-making, which we call risk-sensitive variational Bayes (RSVB). In RSVB, we jointly compute a risk-sensitive approximation to the `true' posterior and the optimal decision by solving a minimax optimization problem. The RSVB framework includes the naive approach of first computing a VI approximation to the true posterior and then using it in place of the true posterior for decision-making. We show that the RSVB approximate posterior and the corresponding optimal value and decision rules are asymptotically consistent, and we also compute their rate of convergence. We illustrate our theoretical findings in both parametric as well as nonparametric setting with the help of three examples: the single and multi-product newsvendor model and Gaussian process classification. Second, we present the Bayesian joint chance-constrained stochastic program (BJCCP) for modeling decision-making problems with epistemically uncertain constraints. We discover that using VI methods for posterior approximation can ensure the convexity of the feasible set in (BJCCP) unlike any sampling-based methods and thus propose a VI approximation for (BJCCP). We also show that the optimal value computed using the VI approximation of (BJCCP) are statistically consistent. Moreover, we derive the rate of convergence of the optimal value and compute the rate at which a VI approximate solution of (BJCCP) is feasible under the true constraints. We demonstrate the utility of our approach on an optimal staffing problem for an M/M/c queue. Finally, this thesis also contributes to the growing literature in understanding statistical performance of VI methods. In particular, we establish the frequentist consistency of an approximate posterior computed using a well known VI method that computes an approximation to the posterior distribution by minimizing the Renyi divergence from the ‘true’ posterior.</div>

No description available.

No description available.

This dissertation develops efficient solution techniques for general and problem-specific applications within nonconvex optimization, exploiting the constructs of the Reformulation-Linearization Technique (RLT). We begin by developing a technique to enhance general problems in nonconvex optimization through the use of a new class of RLT cuts, called semidefinite cuts. While these cuts are valid for any general problem for which RLT is applicable, we demonstrate their effectiveness in optimizing a nonconvex quadratic objective function over a simplex. Computational results indicate that on average, the semidefinite cuts have reduced the number of nodes in the branch-and-bound tree by a factor of 37.6, while decreasing solution time by a factor of 3.4. The semidefinite cuts have also led to a significant reduction in the optimality gap at termination, in some cases producing optimal solutions for problems that could not be solved using RLT alone. We then narrow our focus to the class of mixed-integer programming (MIP) problems, and develop a modification of Benders' decomposition method using concepts from RLT and lift-and-project cuts. This method is particularly motivated by the class of two-stage stochastic programs with integer recourse. The key idea is to design an RLT or lift-and-project cutting plane scheme for solving the subproblems where the cuts generated have right-hand sides that are functions of the first-stage variables. An illustrative example is provided to elucidate the proposed approach. The focus is on developing a first comprehensive finitely convergent extension of Benders' methodology for problems having 0-1 mixed-integer subproblems. We next address a specific challenging MIP application known as the facility layout problem, and we significantly improve its formulation through outer-linearization techniques and concepts from disjunctive programming. The enhancements produce a substantial increase in the accuracy of the layout produced, while at the same time, providing a dramatic reduction in computational effort. Overall, the maximum error in department size was reduced from about 6% to nearly zero, while solution time decreased by a factor of 110. Previously unsolved test problems from the literature that had defied even approximate solution methods have been solved to exact optimality using our proposed approach. / Ph. D.