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.

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.

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.

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

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

This paper presents a novel approach for designing and optimizing maintenance service contracts through the application of mechanism design theory. When offering a contract to its customer, the maintenance service provider seeks to specify contract terms - such as price, service features and incentives - that maximize the provider's profit, satisfy customer needs, allocate risks effectively and mitigate moral hazards. Optimal contract design has to account for asymmetric information and uncertainties associated with customer characteristics and behaviors. We illustrate our mechanism design approach by applying it to the contract design challenge of a gas turbine manufacturer, which also provides maintenance services for its aircraft engines. In our solution approach, we compute an optimal set of contracts. The entire set is presented to the customer and is designed such that the customer will accept one of the contract alternatives without negotiations. In addition to eliminating the costs and delays associated with negotiations, this approach also reveals the customer's private information to the service provider, which the provider can use to its benefit in maintenance management and future contract renewals. Furthermore, we design and incorporate win-win incentive mechanisms into the contracts, which reward the customer for actions that reduces maintenance costs. We present a deterministic and a stochastic mechanism design model, the latter accounting for uncertainties associated with customer actions, engine performance, and maintenance costs during the contract execution phase. / Master of Science

Nous considérons des problèmes d'optimisation stochastique et de théorie des jeux avec des mesures de risque. Dans une première partie, nous mettons l'accent sur la cohérence temporelle. Nous commençons par prouver une équivalence entre cohérence temporelle et l'existence d'une formule imbriquée pour des fonctions. Motivés par des exemples bien connus dans les mesures de risque, nous étudions trois classes de fonctions: les fonctions invariantes par translation, les transformées de Fenchel-Moreau et les fonctions supremum. Ensuite, nous étendons le concept de cohérence temporelle à la cohérence entre joueurs, en remplaçant le temps séquentiel par un ensemble non ordonné et les fonctions par des relations binaires. Enfin, nous montrons comment la cohérence entre joueurs est liée à des formes de décomposition séquentielles et parallèles en optimisation. Dans une seconde partie, nous étudions l'impact des mesures de risque sur la multiplicité des équilibres dans les problèmes de jeux dynamiques dans les marchés complets et incomplets. Nous concevons un exemple où l'introduction de mesures de risque conduit à l'existence de trois équilibres au lieu d'un dans le cas risque neutre. Nous analysons la capacité de deux algorithmes différents à trouver les différents équilibres. Nous discutons des liens entre la cohérence des joueurs et les problèmes d'équilibre dans les jeux. Dans une troisième partie, nous étudions l'optimisation robuste pour l'apprentissage automatique. En utilisant des mesures de risque convexes, nous fournissons un cadre unifié et proposons un algorithme adapté couvrant trois ensembles d'ensembles d'ambiguïté étudiés dans la littérature / We consider stochastic optimization and game theory problems with risk measures. In a first part, we focus on time consistency. We begin by proving an equivalence between time consistent mappings and the existence of a nested formula. Motivated by well-known examples in risk measures, we investigate three classes of mappings: translation invariant, Fenchel-Moreau transform and supremum mappings. Then, we extend the concept of time consistency to player consistency, by replacing the sequential time by any unordered set and mappings by any relations. Finally, we show how player consistency relates to sequential and parallel forms of decomposition in optimization. In a second part, we study how risk measures impact the multiplicity of equilibria in dynamic game problems in complete and incomplete markets. We design an example where the introduction of risk measures leads to the existence of three equilibria instead of one in the risk neutral case. We analyze the ability of two different algorithms to recover the different equilibria. We discuss links between player consistency and equilibrium problems in games. In a third part, we study distribution ally robust optimization in machine learning. Using convex risk measures, we provide a unified framework and propose an adapted algorithm covering three ambiguity sets discussed in the literature

In this thesis we modified a sampling-based motion planning algorithm to improve sampling efficiency. First, we modify the RRT* motion planning algorithm with a local motion planner that guarantees collision-free state trajectories without explicitly checking for collision with obstacles. The control trajectories are generated by solving a sequence of quadratic programs with Control Barrier Functions (CBF) constraints. If the control trajectories satisfy the CBF constraints, the state trajectories are guaranteed to stay in the free subset of the state space. Second, we use a stochastic optimization algorithm to adapt the sampling density function of RRT* to increase the probability of sampling in promising regions in the configuration space. In our approach, we use the nonparametric generalized cross-entropy (GCE) method is used for importance sampling, where a subset of the sampled RRT* trajectories is incrementally exploited to adapt the density function. The modified algorithms, the Adaptive CBF-RRT* and the CBF-RRT*, are demonstrated with numerical examples using the unicycle dynamics. The Adaptive CBF-RRT* has been shown to yield paths with lower cost with fewer tree vertexes than the CBF-RRT*. / 2022-03-27T00:00:00Z