We consider joint chance-constrained programs with random lefthand sides. The motivation of this project is that this class of problem has many important applications, but there are few existing solution methods. For the most part, we deal with the subclass of problems for which the underlying parameter distributions are discrete. This assumption allows the original problem to be formulated as a deterministic equivalent mixed-integer program. We rst approach the problem as a mixed-integer program and derive a class of optimality cuts based on irreducibly infeasible subsets of the constraints of the scenarios of the problem. The IIS cuts can be computed effciently by means of a linear program. We give a method for improving the upper bound of the problem when no IIS cut can be identifi ed. We also give an implementation of an algorithm incorporating these ideas and finish with some computational results. We present a tabu search metaheuristic for fi nding good feasible solutions to the mixed-integer formulation of the problem. Our heuristic works by de ning a sufficient set of scenarios with the characteristic that all other scenarios do not have to be considered when generating upper bounds. We then use tabu search on the one-opt neighborhood of the problem. We give computational results that show our metaheuristic outperforming the state-of-the-art industrial solvers. We then show how to reformulate the problem so that the chance-constraints are monotonic functions. We then derive a convergent global branch-and-bound algorithm using the principles of monotonic optimization. We give a finitely convergent modi cation of the algorithm. Finally, we give a discussion on why this algorithm is computationally ine ffective. The last section of this dissertation details an application of joint chance-constrained stochastic programs to a vaccination allocation problem. We show why it is necessary to formulate the problem with random parameters and also why chance-constraints are a good framework for de fining an optimal policy. We give an example of the problem formulated as a chance constraint and a short numerical example to illustrate the concepts.

An increased penetration of renewable energy into the electric power grid is desirable from an environmental standpoint as well as an economical one. However, renewable sources such as wind and solar energy are often variable and intermittent, and additionally, are non-dispatchable. Also, the locations with the highest amount of available wind or solar may be located in areas that are far from areas with high levels of demand, and these areas may be under the control of separate, individual entities. In this dissertation, a method that coordinates these areas, accounts for the variability and intermittency, reduces the impact of renewable energy forecast errors, and increases the overall social benefit in the system is developed. The approach for the purpose of integrating intermittent energy sources into the electric power grid is considered from both the planning and operations stages. In the planning stage, two-stage stochastic optimization is employed to find the optimal size and location for a storage device in a transmission system with the goal of reducing generation costs, increasing the penetration of wind energy, alleviating line congestions, and decreasing the impact of errors in wind forecasts. The size of this problem grows dramatically with respect to the number of variables and constraints considered. Thus, a scenario reduction approach is developed which makes this stochastic problem computationally feasible. This scenario reduction technique is derived from observations about the relationship between the variance of locational marginal prices corresponding to the power balance equations and the optimal storage size. Additionally, a probabilistic, or chance, constrained model predictive control (MPC) problem is formulated to take into account wind forecast errors in the optimal storage sizing problem. A probability distribution of wind forecast errors is formed and incorporated into the original storage sizing problem. An analytical form of this constraint is derived to directly solve the optimization problem without having to use Monte-Carlo simulations or other techniques that sample the probability distribution of forecast errors. In the operations stage, a MPC AC Optimal Power Flow problem is decomposed with respect to physical control areas. Each area performs an independent optimization and variable values on the border buses between areas are exchanged at each Newton-Raphson iteration. Two modifications to the Approximate Newton Directions (AND) method are presented and used to solve the distributed MPC optimization problem, both with the intention of improving the original AND method by improving upon the convergence rate. Methods are developed to account for numerical difficulties encountered by these formula- tions, specifically with regards to Jacobian singularities introduced due to the intertemporal constraints. Simulation results show convergence of the decomposed optimization problem to the centralized result, demonstrating the benefits of coordinating control areas in the IEEE 57- bus test system. The benefit of energy storage in MPC formulations is also demonstrated in the simulations, reducing the impact of the fluctuations in the power supply introduced by intermittent sources by coordinating resources across control areas. An overall reduction of generation costs and increase in renewable penetration in the system is observed, with promising results to effectively and efficiently integrate renewable resources into the electric power grid on a large scale.

Energy management strategies for microgrids, containing energy storage, renewable energy sources (RES), and electric vehicles (EVs); which interact with the grid on an individual basis; are presented in Chapter 3. An optimization problem to reduce cost, formulated over a rolling time horizon, using predicted values of load demand, EV connection/disconnection times, and charge levels at time of connection, is described. The solution provides the on-site storage and EV charge/discharge powers. For the first time, both bidirectional and unidirectional charging are considered for EVs and a controller which accommodates uncertainties in EV energy levels and connection/disconnection times is presented. In Chapter 4, a stochastic chance constraints based optimization is described. It affords significant improvement in robustness, over the conventional controller, to uncertainties in system parameters. Simulation results demonstrate that the stochastic controller is at least twice as effective at meeting the desired EV charge level at specific times compared to the non-stochastic version, in the presence of uncertainties. In Chapter 5, a network of microgrids, containing RES and batteries, which trade energy among themselves and with the utility grid is considered. A novel distributed energy management system (EMS), based on a central EMS using a Multi-Objective (MO) Rolling Horizon (RH) scheme, is presented. It uses Alternating Direction Method of Multipliers (ADMM) and Quadratic Programming (QP). It is inherently more data-secure and resilient to communication issues than the central EMS. It is shown that using an EMS in the network provides significant economic benefits over MGs connected directly to the grid. Simulations demonstrate that the distributed scheme produced solutions which are very close to those of the central EMS. Simulation results also reveal that the faster, less memory intensive distributed scheme is scalable to larger networks -- more than 1000 microgrids as opposed to a few hundreds for the central EMS. / Thesis / Doctor of Philosophy (PhD)

While optimization problems are ubiquitous in all domains of engineering, they are of critical importance to power systems engineers. A safe and economical operation of the power systems entails solving many optimization problems such as security-constrained unit commitment, economic dispatch, optimal power flow, optimal planning, etc. Although traditional optimization solvers and software have been successful so far in solving these problems, there is a growing need to accelerate the solution process. This need arises on account of several aspects of grid modernization, such as distributed energy resources, renewable energy, smart inverters, batteries, etc, that increase the number of decision variables involved. Moreover, the technologies entail faster dynamics and unpredictability, further demanding a solution speedup. Yet another concern is the growing communication overhead that accompanies this large-scale, high-speed, decision-making process. This thesis explores three different directions to address such concerns. The first part of the thesis explores the learning-to-optimize paradigm whereby instead of solving the optimization problems, machine learning (ML) models such as deep neural networks (DNNs) are trained to predict the solution of the optimization problems. The second part of the thesis also employs deep learning, but in a different manner. DNNs are utilized to model the dynamics of IEEE 1547.8 standard-based local Volt/VAR control rules, and then leverage efficient deep learning libraries to solve the resulting optimization problem. The last part of the thesis dives into the evolving field of quantum computing and develops a general strategy for solving stochastic binary optimization problems using variational quantum eigensolvers (VQE). / Doctor of Philosophy / A reliable and economical operation of power systems entails solving large-scale decision-making mathematical problems, termed as optimization problems. Modern additions to power systems demand an acceleration of this decision-making process while managing the accompanying communication overheads efficiently. This thesis explores the application of two recent advancements in computer science -- machine learning (ML) and quantum computing (QC), to address the above needs. The research presented in this thesis can be divided into three parts. The first part proposes replacing conventional mathematical solvers for optimization problems, with ML models that can predict the solutions to these solvers. Colloquially referred to as learning-to-optimize, this paradigm learns from a historical dataset of good solutions and extrapolates them to make new decisions in a fast manner, while requiring potentially limited data. The second part of the thesis also uses ML models, but differently. ML models are used to represent the underlying physical dynamics, and convert an originally challenging optimization problem into a simpler one. The new problem can be solved efficiently using popular ML toolkits. The third and final part of the thesis aims at accelerating the process of finding optimal binary decisions under constraints, using QC.

We describe Employees Provident Funds (EPF) Malaysia. We explain about Defined Contribution and Defined Benefit Pension Funds and examine their similarities and differences. We also briefly discuss and compare EPF schemes in four Commonwealth countries. A family of Stochastic Programming Models is developed for the Employees Provident Fund Malaysia. This is a family of ex-ante decision models whose main aim is to manage, that is, balance assets and liabilities. The decision models comprise Expected Value Linear Programming, Two Stage Stochastic Programming with recourse, Chance Constrained Programming and Integrated Chance Constraints Programming. For the last three decision models we use scenario generators which capture the uncertainties of asset returns, salary contributions and lump sum liabilities payments. These scenario generation models for Assets and liabilities were developed and calibrated using historical data. The resulting decisions are evaluated with in-sample analysis using typical risk adjusted performance measures. Out- of- sample testing is also carried out with a larger set of generated scenarios. The benefits of two stage stochastic programming over deterministic approaches on asset allocation as well as the amount of borrowing needed for each pre-specified growth dividend are demonstrated. The contributions of this thesis are i) an insightful overview of EPF ii) construction of scenarios for assets returns and liabilities with different values of growth dividend, that combine the Markov population model with the salary growth model and retirement payments iii) construction and analysis of generic ex-ante decision models taking into consideration uncertain asset returns and uncertain liabilities iv) testing and performance evaluation of these decisions in an ex-post setting.

In this dissertation we study several non-convex and stochastic optimization problems. The common theme is the use of mixed-integer programming (MIP) techniques including valid inequalities and reformulation to solve these problems. We first study a strategic capacity planning model which captures the trade-off between the incentive to delay capacity installation to wait for improved technology and the need for some capacity to be installed to meet current demands. This problem is naturally formulated as a MIP with a bilinear objective. We develop several linear MIP formulations, along with classes of strong valid inequalities. We also present a specialized branch-and-cut algorithm to solve a compact concave formulation. Computational results indicate that these formulations can be used to solve large-scale instances. We next study methods for optimization with joint probabilistic constraints. These problems are challenging because evaluating solution feasibility requires multidimensional integration and the feasible region is not convex. We propose and analyze a Monte Carlo sampling scheme to simplify the probabilistic structure of such problems. Computational tests of the approach indicate that it can yield good feasible solutions and reasonable bounds on their quality. Next, we study a MIP formulation of the non-convex sample approximation problem. We obtain two strengthened formulations. As a byproduct of this analysis, we obtain new results for the previously studied mixing set, subject to an additional knapsack inequality. Computational results indicate that large-scale instances can be solved using the strengthened formulations. Finally, we study optimization problems with stochastic dominance constraints. A stochastic dominance constraint states that a random outcome which depends on the decision variables should stochastically dominate a given random variable. We present new formulations for both first and second order stochastic dominance which are significantly more compact than existing formulations. Computational tests illustrate the benefits of the new formulations.

[pt] Estudamos aproximações amostrais de problemas com restrições probabilísticas através da aproximação pela média amostral (SAA) e demonstramos as propriedades de convergência relacionadas. Utilizamos SAA para obter bons candidatos à solução e cotas estatísticas para o valor ótimo do problema original. Para ajustar corretamente parâmetros, aplicamos o método a dois problemas com restrições probabilísticas. O primeiro é um problema de seleção de portfolio linear com retornos seguindo uma distribuição lognormal multivariada. O segundo é uma versão com restrições probabilísticas conjuntas de um problema da mistura simplificado. Concluímos com uma aplicação mais exigente ao problema de se determinar a provisão mínima que um agente econômico deve ter de forma a satisfazer uma série de obrigações futuras com probabilidade suficientemente alta. / [en] We study sample approximations of chance constrained problems through the sample average approximation (SAA) approach and prove the related convergence properties. We discuss how to use the SAA method to obtain good candidate solutions and bounds for the optimal value of the original problem. In order to tune the parameters of SAA, we apply the method to two chance constrained problems. The first is a linear portfolio selection problem with returns following a multivariate lognormal distribution. The second is a joint chance constrained version of a simple blending problem. We conclude with a more demanding application of SAA methodology to the determination of the minimum provision an economic agent must have in order to meet a series of future payment obligations with sufficiently high probability.

abstract: Project portfolio selection (PPS) is a significant problem faced by most organizations. How to best select the many innovative ideas that a company has developed to deploy in a proper and sustained manner with a balanced allocation of its resources over multiple time periods is one of vital importance to a company's goals. This dissertation details the steps involved in deploying a more intuitive portfolio selection framework that facilitates bringing analysts and management to a consensus on ongoing company efforts and buy into final decisions. A binary integer programming selection model that constructs an efficient frontier allows the evaluation of portfolios on many different criteria and allows decision makers (DM) to bring their experience and insight to the table when making a decision is discussed. A binary fractional integer program provides additional choices by optimizing portfolios on cost-benefit ratios over multiple time periods is also presented. By combining this framework with an `elimination by aspects' model of decision making, DMs evaluate portfolios on various objectives and ensure the selection of a portfolio most in line with their goals. By presenting a modeling framework to easily model a large number of project inter-dependencies and an evolutionary algorithm that is intelligently guided in the search for attractive portfolios by a beam search heuristic, practitioners are given a ready recipe to solve big problem instances to generate attractive project portfolios for their organizations. Finally, this dissertation attempts to address the problem of risk and uncertainty in project portfolio selection. After exploring the selection of portfolios based on trade-offs between a primary benefit and a primary cost, the third important dimension of uncertainty of outcome and the risk a decision maker is willing to take on in their quest to select the best portfolio for their organization is examined. / Dissertation/Thesis / Doctoral Dissertation Industrial Engineering 2018

Le problème généralisé des moments (PGM) est un problème d'optimisation linéaire sur des espaces de mesures. Il permet de modéliser simplement un grand nombre d'applications. En toute généralité il est impossible à résoudre mais si ses données sont des polynômes et des ensembles semi-algébriques alors on peut définir une hiérarchie de relaxations semidéfinies (SDP) - la hiérarchie moments-sommes-de-carrés (moments-SOS) - qui permet en principe d'approcher la valeur optimale avec une précision arbitraire. Le travail contenu dans cette thèse adresse deux facettes concernants le PGM et la hiérarchie moments-SOS: Une première facette concerne l'évolution des relaxations SDP pour le PGM. Le degré des poids SOS dans la hiérarchie moments-SOS augmente avec l'ordre de relaxation. Lorsque le nombre de variables n'est pas modeste, on obtient rapidement des programmes SDP de taille trop grande pour les logiciels de programmation SDP actuels, sauf si l'on peut utiliser des symétries ou une parcimonie structurée souvent présente dans beaucoup d'applications de grande taille. On présente donc un nouveau certificat de positivité sur un compact semi-algébrique qui (i) exploite la parcimonie présente dans sa description, et (ii) dont les polynômes SOS ont un degré borné à l'avance. Grâce à ce nouveau certificat on peut définir une nouvelle hiérarchie de relaxations SDP pour le PGM qui exploite la parcimonie et évite l'explosion de la taille des matrices semidéfinies positives liée au degré des poids SOS dans la hiérarchie standard. Une deuxième facette concerne (i) la modélisation de nouvelles applications comme une instance particulière du PGM, et (ii) l'application de la méthodologie moments-SOS pour leur résolution. En particulier on propose des approximations déterministes de contraintes probabilistes, un problème difficile car le domaine des solutions admissibles associées est souvent non-convexe et même parfois non connecté. Dans notre approche moments-SOS le domaine admissible est remplacé par un ensemble plus petit qui est le sous-niveau d'un polynôme dont le vecteur des coefficients est une solution optimale d'un certain SDP. La qualité de l'approximation (interne) croît avec le degré du polynôme et la taille du SDP. On illustre cette approche dans le problème du calcul du flux de puissance optimal dans les réseaux d'énergie, une application stratégique où la prise en compte des contraintes probabilistes devient de plus en plus cruciale (e.g., pour modéliser l'incertitude liée á l'énergie éolienne et solaire). En outre on propose une extension des cette procedure qui est robuste à l'incertitude sur la distribution sous-jacente. Des garanties de convergence sont fournies. Une deuxième contribution concerne l'application de la méthodologie moments-SOS pour l'approximation de solutions généralisés en commande optimale. Elle permet de capturer le comportement limite d'une suite minimisante de commandes et de la suite de trajectoires associée. On peut traiter ainsi le cas de phénomènes simultanés de concentrations de la commande et de discontinuités de la trajectoire. Une troisième contribution concerne le calcul de solutions mesures pour les lois de conservation hyperboliques scalaires dont l'exemple typique est l'équation de Burgers. Cette classe d'EDP non linéaire peut avoir des solutions discontinues difficiles à approximer numériquement avec précision. Sous certaines hypothèses, la solution mesurepeut être identifiée avec la solution classique (faible) à la loi de conservation. Notre approche moment-SOS fournit alors une méthode alternative pour approcher des solutions qui contrairement aux méthodes existantes évite une discrétisation du domaine. / The generalized moment problem (GMP) is a linear optimization problem over spaces of measures. It allows to model many challenging mathematical problems. While in general it is impossible to solve the GMP, in the case where all data are polynomial and semialgebraic sets, one can define a hierarchy of semidefinite relaxations - the moment-sums-of-squares (moment-SOS) hierachy - which in principle allows to approximate the optimal value of the GMP to arbitrary precision. The work presented in this thesis addresses two facets concerning the GMP and the moment-SOS hierarchy: One facet is concerned with the scalability of relaxations for the GMP. The degree of the SOS weights in the moment-SOS hierarchy grows when augmenting the relaxation order. When the number of variables is not small, this leads quickly to semidefinite programs (SDPs) that are out of range for state of the art SDP solvers, unless one can use symmetries or some structured sparsity which is typically present in large scale applications. We provide a new certificate of positivity which (i) is able to exploit the structured sparsity and (ii) only involves SOS polynomials of fixed degree. From this, one can define a new hierarchy of SDP relaxations for the GMP which can take into account sparsity and at the same time prevents from explosion of the size of SDP variables related to the increasing degree of the SOS weights in the standard hierarchy. The second facet focusses on (i) modelling challenging problems as a particular instance of the GMP and (ii) solving these problems by applying the moment-SOS hierarchy. In particular we propose deterministic approximations of chance constraints a difficult problem as the associated set of feasible solutions is typically non-convex and sometimes not even connected. In our approach we replace this set by a (smaller) sub-level-set of a polynomial whose vector of coefficients is a by-product of the moment-SOS hierarchy when modeling the problem as an instance of the GMP. The quality of this inner approximation improves when increasing the degree of the SDP relaxation and asymptotic convergence is guaranteed. The procedure is illustrated by approximating the feasible set of an instance of the chance-constrained AC Optimal Power Flow problem (a nonlinear problem in the management of energy networks) which nowadays becomes more and more important as we rely increasingly on uncertain energy sources such as wind and solar power. Furthermore, we propose an extension of this framework to the case where the underlying distribution itself is uncertain and provide guarantees of convergence. Another application of the moment-SOS methodology discussed in this thesis consider measure valued solutions to optimal control problems. We show how this procedure can capture the limit behavior of an optimizing sequence of control and its corresponding sequence of trajectories. In particular we address the case of concentrations of control and discontinuities of the trajectory may occur simultaneously. In a final contribution, we compute measure valued solutions to scalar hyperbolic conservation laws, such as Burgers equation. It is known that this class of nonlinear partial differential equations has potentially discontinuous solutions which are difficult to approximate numerically with accuracy. Under some conditions the measure valued solution can be identified with the classical (weak) solution to the conservation law. In this case our moment-SOS approach provides an alternative numerical scheme to compute solutions which in contrast to existing methods, does not rely on discretization of the domain.

No description available.