To reduce domestic military infrastructure, the United States enacted two laws that instituted rounds of base realignment and closure (BRAC) in 1988, 1991, 1993, and 1995. As a result of these BRAC rounds, the United States Army has closed or realigned 139 installations. Environmental cleanup is almost $2.3 billion (43%) of the entire cost associated with the closure and realignment of these 139 Army installations. The United States Army Base Realignment and Closure Office (BRACO) uses an integer linear program called BAEC (Budget Allocation for Environmental Cleanup) to help determine how to allocate limited yearly funding to installations for environmental cleanup. Considering environmental policies and yearly installation funding requests from 2002 to 2015, this thesis modifies BAEC to better account for uncertainty in future environmental cleanup cost estimates. Based on historic data that show most environmental cleanup cost estimates increase over time, the stochastic BAEC model recommends funding fewer sites than the deterministic BAEC model recommends. The stochastic BAEC model thereby provides funding recommendations with a better chance of staying within limited available yearly funding. / Turkish Army author
(has links) (PDF)
Thesis (M.S. in Operations Research) Naval Postgraduate School, December 2001. / Thesis Advisor (s): Dell, Robert F. "December 2001." Includes bibliographical references (p. 35). Also available online.
29 September 2010
This dissertation focuses on three cases of the following two stage problem in the context of multi-product inventories of vertically differentiated products. In Stage 1 of the problem, the manager determines the optimal production quantities of different products when the demands are uncertain. In Stage 2 of the problem, the demands for different products are observed. Now, the manager meets the demand of each product using the inventory of the product or by carrying out a downward substitution from the inventories of higher performance products. The manager’s objective is to maximize the expected revenue from the decisions made at the two stages collectively. The first problem addressed in this dissertation focuses on the case when different products are produced simultaneously on the same set of machines due to random variations in the manufacturing process. These systems, referred to as co-production systems, are very common in the semi- conductor industry, the textile industry and the agriculture industry. For this problem, we provide an analytical solution to the two stage problem, and discuss managerial insights that are specific to co-production systems and are not extendible to multi-item inventories of products that can be ordered or manufactured independently. The second problem addressed in this dissertation focuses on the case when different products can be ordered or manufactured independently, and no constraints to meet minimum fill rate requirements or to restrict the total inventory below a certain level are present. We present an analytical solution to this problem. The third problem addressed in this dissertation focuses on the case when different products can be ordered or manufactured independently and fill rate constraints and total inventory constraints are present. When the demands are multivariate normal, we show that this two stage problem can be reduced to a non-linear program using some new results for the determination of partial expectations. We also extend these results to higher order moments of the multivariate distribution and discuss their applications in solving some common operations management problems. / text
Ant Colony Optimization and Local Search for the Probabilistic Traveling Salesman Problem: A Case Study in Stochastic Combinatorial OptimizationBianchi, Leonora 29 June 2006 (has links)
In this thesis we focus on Stochastic combinatorial Optimization Problems (SCOPs), a wide class of combinatorial optimization problems under uncertainty, where part of the information about the problem data is unknown at the planning stage, but some knowledge about its probability distribution is assumed. Optimization problems under uncertainty are complex and difficult, and often classical algorithmic approaches based on mathematical and dynamic programming are able to solve only very small problem instances. For this reason, in recent years metaheuristic algorithms such as Ant Colony Optimization, Evolutionary Computation, Simulated Annealing, Tabu Search and others, are emerging as successful alternatives to classical approaches. In this thesis, metaheuristics that have been applied so far to SCOPs are introduced and the related literature is thoroughly reviewed. In particular, two properties of metaheuristics emerge from the survey: they are a valid alternative to exact classical methods for addressing real-sized SCOPs, and they are flexible, since they can be quite easily adapted to solve different SCOPs formulations, both static and dynamic. On the base of the current literature, we identify the following as the key open issues in solving SCOPs via metaheuristics: (1) the design and integration of ad hoc, fast and effective objective function approximations inside the optimization algorithm; (2) the estimation of the objective function by sampling when no closed-form expression for the objective function is available, and the study of methods to reduce the time complexity and noise inherent to this type of estimation; (3) the characterization of the efficiency of metaheuristic variants with respect to different levels of stochasticity in the problem instances. We investigate the above issues by focusing in particular on a SCOP belonging to the class of vehicle routing problems: the Probabilistic Traveling Salesman Problem (PTSP). For the PTSP, we consider the Ant Colony Optimization metaheuristic and we design efficient local search algorithms that can enhance its performance. We obtain state-of-the-art algorithms, but we show that they are effective only for instances above a certain level of stochasticity, otherwise it is more convenient to solve the problem as if it were deterministic. The algorithmic variants based on an estimation of the objective function by sampling obtain worse results, but qualitatively have the same behavior of the algorithms based on the exact objective function, with respect to the level of stochasticity. Moreover, we show that the performance of algorithmic variants based on ad hoc approximations is strongly correlated with the absolute error of the approximation, and that the effect on local search of ad hoc approximations can be very degrading. Finally, we briefly address another SCOP belonging to the class of vehicle routing problems: the Vehicle Routing Problem with Stochastic Demands (VRPSD). For this problem, we have implemented and tested several metaheuristics, and we have studied the impact of integrating in them different ad hoc approximations.
Bhavsar, Sujal Pradipkumar
19 September 2022
In an attempt to thwart global warming in a concerted way, more than 130 countries have committed to becoming carbon neutral around 2050. In the United States, the Biden ad- ministration has called for 100% clean energy by 2035. It is estimated that in order to meet that target, the energy production from solar and wind should increase to 50-70% from the current 11% share. Under higher penetration of solar and wind, the intermittency of the energy source poses critical problems in forecasting, uncertainty quantification, reserve man- agement, unit commitment, and economic dispatch, and presents unique challenges to the distribution system, including predicting solar adoption by the user as well as forecasting end-use load profiles. While these problems are complex, advances in machine learning and artificial intelligence provide opportunities for novel paradigms for addressing the challenges. The overall aim of the dissertation is to harness data-driven and model-based techniques and develop computationally efficient tools for improved power systems operation under high re- newables penetration in the next-generation electric grid. Some of the salient contributions of this work are the reduction in the number of uncertain scenarios by 99%; dramatic reduc- tion in the computational overhead to simulate stochastic unit commitment and economic dispatch on a single-node electric-grid system to merely 10 seconds from 24 hours; reduc- tion in the total monthly operating cost of two-stage stochastic economic dispatch by an average of 5%, and reduction in average overall reserve due to intermittency in renewables by 50%; and improvement in the existing end-use load prediction and rooftop PV adopter identification tools by a considerable margin. / Doctor of Philosophy / In an attempt to thwart global warming in a concerted way, more than 130 countries have committed to becoming carbon neutral around 2050. In the United States, the Biden ad- ministration has called for 100% clean energy by 2035. It is estimated that in order to meet that target, the energy production from solar and wind should increase to 50-70% from the current 11% share. Under higher penetration of solar and wind, the intermittency of the energy source poses critical problems in forecasting, uncertainty quantification, reserve man- agement, unit commitment, and economic dispatch, and presents unique challenges to the distribution system, including predicting solar adoption by the user as well as forecasting end-use load profiles. While these problems are complex, advances in machine learning and artificial intelligence provide opportunities for novel paradigms for addressing the challenges. The overall aim of the dissertation is to harness data-driven and model-based techniques and develop computationally efficient tools for improved power systems operation under high re- newables penetration in the next-generation electric grid. Some of the salient contributions of this work are the reduction in the number of uncertain scenarios by 99%; dramatic reduc- tion in the computational overhead to simulate stochastic unit commitment and economic dispatch on a single-node electric-grid system to merely 10 seconds from 24 hours; reduc- tion in the total monthly operating cost of two-stage stochastic economic dispatch by an average of 5%, and reduction in average overall reserve due to intermittency in renewables by 50%; and improvement in the existing end-use load prediction and rooftop PV adopter identification tools by a considerable margin.
21 September 2015
Integrated assessment models are powerful tools for providing insight into the interaction between the economy and climate change over a long time horizon. However, knowledge of climate parameters and their behavior under extreme circumstances of global warming is still an active area of research. In this thesis we incorporated the uncertainty in one of the key parameters of climate change, climate sensitivity, into an integrated assessment model and showed how this affects the choice of optimal policies and actions. We constructed a new, multi-step-ahead approximate dynamic programing (ADP) algorithm to study the effects of the stochastic nature of climate parameters. We considered the effect of stochastic extreme events in climate change (tipping points) with large economic loss. The risk of an extreme event drives tougher GHG reduction actions in the near term. On the other hand, the optimal policies in post-tipping point stages are similar to or below the deterministic optimal policies. Once the tipping point occurs, the ensuing optimal actions tend toward more moderate policies. Previous studies have shown the impacts of economic and climate shocks on the optimal abatement policies but did not address the correlation among uncertain parameters. With uncertain climate sensitivity, the risk of extreme events is linked to the variations in climate sensitivity distribution. We developed a novel Bayesian framework to endogenously interrelate the two stochastic parameters. The results in this case are clustered around the pre-tipping point optimal policies of the deterministic climate sensitivity model. Tougher actions are more frequent as there is more uncertainty in likelihood of extreme events in the near future. This affects the optimal policies in post-tipping point states as well, as they tend to utilize more conservative actions. As we proceed in time toward the future, the (binary) status of the climate will be observed and the prior distribution of the climate sensitivity parameter will be updated. The cost and climate tradeoffs of new technologies are key to decisions in climate policy. Here we focus on electricity generation industry and contrast the extremes in electricity generation choices: making choices on new generation facilities based on cost only and in the absence of any climate policy, versus making choices based on climate impacts only regardless of the generation costs. Taking the expected drop in cost as experience grows into account when selecting the portfolio of generation, on a pure cost-minimization basis, renewable technologies displace coal and natural gas within two decades even when climate damage is not considered in the choice of technologies. This is the natural gas as a bridge fuel scenario, and technology advancement to bring down the cost of renewables requires some commitment to renewables generation in the near term. Adopting the objective of minimizing climate damage, essentially moving immediately to low greenhouse gas generation technologies, results in faster cost reduction of new technologies and may result in different technologies becoming dominant in global electricity generation. Thus today’s choices for new electricity generation by individual countries and utilities have implications not only for their direct costs and the global climate, but also for the future costs and availability of emerging electricity generation options.
07 December 2010
This research focuses on finding the optimal maintenance policy for an item with varying failure behavior. We analyze several types of item failure rates and develop methods to solve for optimal maintenance schedules. We also illustrate nonparametric modeling techniques for failure rates, and utilize these models in the optimization methods. The general problem falls under the umbrella of stochastic optimization under uncertainty. / text
01 May 2012
The focus of this thesis is on the design and analysis of algorithms for basic problems in Stochastic Optimization, specifically a class of fundamental combinatorial optimization problems where there is some form of uncertainty in the input. Since many interesting optimization problems are computationally intractable (NP-Hard), we resort to designing approximation algorithms which provably output good solutions. However, a common assumption in traditional algorithms is that the exact input is known in advance. What if this is not the case? What if there is uncertainty in the input? With the growing size of input data and their typically distributed nature (e.g., cloud computing), it has become imperative for algorithms to handle varying forms of input uncertainty. Current techniques, however, are not robust enough to deal with many of these problems, thus necessitating the need for new algorithmic tools. Answering such questions, and more generally identifying the tools for solving such problems, is the focus of this thesis. The exact problems we study in this thesis are the following: (a) the Survivable Network Design problem where the collection of (source,sink) pairs is drawn randomly from a known distribution, (b) the Stochastic Knapsack problem with random sizes/rewards for jobs, (c) the Multi-Armed Bandits problem, where the individual Markov Chains make random transitions, and finally (d) the Stochastic Orienteering problem, where the random tasks/jobs are located at different vertices on a metric. We explore different techniques for solving these problems and present algorithms for all the above problems with near-optimal approximation guarantees. We also believe that the techniques are fairly general and have wider applicability than the context in which they are used in this thesis.
Position information is important for various applications, including location-aware communications, autonomous driving, industrial internet of things (IoT). Geometry based techniques such as time-of-arrival (TOA), time-difference-of-arrival (TDOA), and angle-of-arrival (AOA) are widely used and can be formed as optimization prob lems. In order to solve these optimization problems efficiently, stochastic optimization methods are discussed in this work in solving target positioning problems and tackling key issues in location-based applications. Firstly, the direction of arrival (DOA) estimation problem is studied in this work. Grid search is useful in the algorithms such as maximum likelihood estimator (MLE), MUltiple SIgnal Classification (MUSIC), etc. However, the computational cost is the main drawback. To speed up the search procedure, we implement random ferns to extract the features from the beampatterns of different DOAs and use these features to identify potential angle candidates. Then, we propose an ultrasonic air-writing system based on DOA estimation. In this application, stochastic optimization methods are implemented to solve gesture classification problems. This work shows that stochastic optimization methods are effective tools to address and benchmark practical positioning-related problems. Next, we discuss how to select antennas properly to reduce the expectation of DOA estimation error in a switch-based multiple-input-multiple-output (MIMO) system. Cram`er Rao lower bound (CRLB) expresses a lower bound on the variance of an unbiased estimator, but it does not work well for low SNR scenarios. We use DOA threshold-region approximation as an indicator and propose a greedy algorithm and a neural network-based algorithm. Finally, we propose a joint time difference of arrival (TDOA) and phase difference of arrival (PDOA) localization method. It is shown that the phase difference, which is also widely used in DOA estimation, can improve the performance of the well established TDOA technique. Although the joint TDOA/PDOA cost function has a lot of local minima, accurate estimates can be obtained effectively by choosing an appropriate initial estimation and using particle swarm optimization (PSO).
The thesis studies the problem well-known in literature as the newsvendor problem. After summarizing the basic model we pay attention to two extensions of this problem and their combination in single model. The first extension concerns the possibility of the vendor to choose his selling price. The second extension is creation of market with several vendors. We describe both situations in the first chapter of the thesis. In the second chapter we study the combination of both extensions, which means the market with several vendors who can choose their selling prices. We touched several models of such market and we found that the problem is very complex. However we found the optimal reaction of one vendor on the strategy of the other vendor in case of special market with two vendors. That enabled us to create a programme that examines such market, mainly the dependence of the optimal decision of one vendor on the strategy of the second vendor and presence of the Nash equilibriums. 1
Page generated in 0.1436 seconds