Search

The inherent nonlinearity of the power flow equations poses significant challenges in accurately modeling power systems, particularly when employing linearized approximations. Although power flow linearizations provide computational efficiency, they can fail to fully capture nonlinear behavior across diverse operating conditions. To improve approximation accuracy, we propose conservative piecewise linear approximations (CPLA) of the power flow equations, which are designed to consistently over- or under-estimate the quantity of interest, ensuring conservative behavior in optimization. The flexibility provided by piecewise linear functions can yield improved accuracy relative to standard linear approximations. However, applying CPLA across all dimensions of the power flow equations could introduce significant computational complexity, especially for large-scale optimization problems. In this paper, we propose a strategy that selectively targets dimensions exhibiting significant nonlinearities. Using a second-order sensitivity analysis, we identify the directions where the power flow equations exhibit the most significant curvature and tailor the CPLAs to improve accuracy in these specific directions. This approach reduces the computational burden while maintaining high accuracy, making it particularly well-suited for mixed-integer programming problems involving the power flow equations.

Physically motivated stochastic dynamics are often used to sample from high-dimensional distributions. However such dynamics often get stuck in specific regions of their state space and mix very slowly to the desired stationary state. This causes such systems to approximately sample from a metastable distribution which is usually quite different from the desired, stationary distribution of the dynamic. We rigorously show that, in the case of multi-variable discrete distributions, the true model describing the stationary distribution can be recovered from samples produced from a metastable distribution under minimal assumptions about the system. This follows from a fundamental observation that the single-variable conditionals of metastable distributions that satisfy a strong metastability condition are on average close to those of the stationary distribution. This holds even when the metastable distribution differs considerably from the true model in terms of global metrics like Kullback-Leibler divergence or total variation distance. This property allows us to learn the true model using a conditional likelihood based estimator, even when the samples come from a metastable distribution concentrated in a small region of the state space. Explicit examples of such metastable states can be constructed from regions that effectively bottleneck the probability flow and cause poor mixing of the Markov chain. For specific cases of binary pairwise undirected graphical models (i.e. Ising models), we extend our results to further rigorously show that data coming from metastable states can be used to learn the parameters of the energy function and recover the structure of the model., Comment: Updated version, 31 pages

Constrained optimization problems arise in various engineering system operations such as inventory management and electric power grids. However, the requirement to repeatedly solve such optimization problems with uncertain parameters poses a significant computational challenge. This work introduces a learning scheme using Bayesian Neural Networks (BNNs) to solve constrained optimization problems under limited labeled data and restricted model training times. We propose a semi-supervised BNN for this practical but complex regime, wherein training commences in a sandwiched fashion, alternating between a supervised learning step (using labeled data) for minimizing cost, and an unsupervised learning step (using unlabeled data) for enforcing constraint feasibility. Both supervised and unsupervised steps use a Bayesian approach, where Stochastic Variational Inference is employed for approximate Bayesian inference. We show that the proposed semi-supervised learning method outperforms conventional BNN and deep neural network (DNN) architectures on important non-convex constrained optimization problems from energy network operations, achieving up to a tenfold reduction in expected maximum equality gap and halving the optimality and inequality (feasibility) gaps, without requiring any correction or projection step. By leveraging the BNN's ability to provide posterior samples at minimal computational cost, we demonstrate that a Selection via Posterior (SvP) scheme can further reduce equality gaps by more than 10%. We also provide tight and practically meaningful probabilistic confidence bounds that can be constructed using a low number of labeled testing data and readily adapted to other applications.

The emergence of quantum computing technology over the last decade indicates the potential for a transformational impact in the study of quantum mechanical systems. It is natural to presume that such computing technologies would be valuable to large scientific institutions, such as United States national laboratories. However, detailed descriptions of what these institutions would like to use these computers for are limited. To help provide some initial insights into this topic, this report develops detailed use cases of how quantum computing technology could be utilized to enhance a variety of quantum physics research activities at Los Alamos National Laboratory, including quantum magnetic materials, high-temperature superconductivity and nuclear astrophysics simulations. The report discusses how current high-performance computers are used for scientific discovery today and develops detailed descriptions of the types of quantum physics simulations that Los Alamos National Laboratory scientists would like to conduct, if a sufficient computing technology became available. While the report strives to highlight the breadth of potential application areas for quantum computation, this investigation has also indicated that many more use cases exist at Los Alamos National Laboratory, which could be documented in similar detail with sufficient time and effort.

Analog Quantum Computers are promising tools for improving performance on applications such as modeling behavior of quantum materials, providing fast heuristic solutions to optimization problems, and simulating quantum systems. Due to the challenges of simulating dynamic quantum systems, there are relatively few classical tools for modeling the behavior of these devices and verifying their performance. QuantumAnnealing.jl provides a toolkit for performing simulations of Analog Quantum Computers on classical hardware. This package includes functionality for simulation of the time evolution of the Transverse Field Ising Model, replicating annealing schedules used by real world annealing hardware, implementing custom annealing schedules, and more. This allows for rapid prototyping of models expected to display interesting behavior, verification of the performance of quantum devices, and easy comparison against the expected behavior of quantum devices against classical approaches for small systems. The software is provided as open-source and is available through Julia's package registry system., Comment: 10 pages, 15 figures

The power flow equations are central to many problems in power system planning, analysis, and control. However, their inherent non-linearity and non-convexity present substantial challenges during problem-solving processes, especially for optimization problems. Accordingly, linear approximations are commonly employed to streamline computations, although this can often entail compromises in accuracy and feasibility. This paper proposes an approach termed Conservative Bias Linear Approximations (CBLA) for addressing these limitations. By minimizing approximation errors across a specified operating range while incorporating conservativeness (over- or under-estimating quantities of interest), CBLA strikes a balance between accuracy and tractability by maintaining linear constraints. By allowing users to design loss functions tailored to the specific approximated function, the bias approximation approach significantly enhances approximation accuracy. We illustrate the effectiveness of our proposed approach through several test cases.

The power flow equations are fundamental to power system planning, analysis, and control. However, the inherent non-linearity and non-convexity of these equations present formidable obstacles in problem-solving processes. To mitigate these challenges, recent research has proposed adaptive power flow linearizations that aim to achieve accuracy over wide operating ranges. The accuracy of these approximations inherently depends on the curvature of the power flow equations within these ranges, which necessitates considering second-order sensitivities. In this paper, we leverage second-order sensitivities to both analyze and improve power flow approximations. We evaluate the curvature across broad operational ranges and subsequently utilize this information to inform the computation of various sample-based power flow approximation techniques. Additionally, we leverage second-order sensitivities to guide the development of rational approximations that yield linear constraints in optimization problems. This approach is extended to enhance accuracy beyond the limitations of linear functions across varied operational scenarios.

Solving linear systems is at the foundation of many algorithms. Recently, quantum linear system algorithms (QLSAs) have attracted great attention since they converge to a solution exponentially faster than classical algorithms in terms of the problem dimension. However, low-complexity circuit implementations of the oracles assumed in these QLSAs constitute the major bottleneck for practical quantum speed-up in solving linear systems. In this work, we focus on the application of QLSAs for linear systems that are expressed as a low rank tensor sums, which arise in solving discretized PDEs. Previous works uses modified Krylov subspace methods to solve such linear systems with a per-iteration complexity being polylogarithmic of the dimension but with no guarantees on the total convergence cost. We propose a quantum algorithm based on the recent advances on adiabatic-inspired QLSA and perform a detailed analysis of the circuit depth of its implementation. We rigorously show that the total complexity of our implementation is polylogarithmic in the dimension, which is comparable to the per-iteration complexity of the classical heuristic methods.

Natural gas consumption by users of pipeline networks is subject to increasing uncertainty that originates from the intermittent nature of electric power loads serviced by gas-fired generators. To enable computationally efficient optimization of gas network flows subject to uncertainty, we develop a finite volume representation of stochastic solutions of hyperbolic partial differential equation (PDE) systems on graph-connected domains with nodal coupling and boundary conditions. The representation is used to express the physical constraints in stochastic optimization problems for gas flow allocation subject to uncertain parameters. The method is based on the stochastic finite volume approach that was recently developed for uncertainty quantification in transient flows represented by hyperbolic PDEs on graphs. In this study, we develop optimization formulations for steady-state gas flow over actuated transport networks subject to probabilistic constraints. In addition to the distributions for the physical solutions, we examine the dual variables that are produced by way of the optimization, and interpret them as price distributions that quantify the financial volatility that arises through demand uncertainty modeled in an optimization-driven gas market mechanism. We demonstrate the computation and distributional analysis using a single-pipe example and a small test network.

Quantum computers hold promise for solving problems intractable for classical computers, especially those with high time and/or space complexity. The reduction of the power flow (PF) problem into a linear system of equations, allows formulation of quantum power flow (QPF) algorithms, based on quantum linear system solving methods such as the Harrow-Hassidim-Lloyd (HHL) algorithm. The speedup due to QPF algorithms is claimed to be exponential when compared to classical PF solved by state-of-the-art algorithms. We investigate the potential for practical quantum advantage (PQA) in solving QPF compared to classical methods on gate-based quantum computers. We meticulously scrutinize the end-to-end complexity of QPF, providing a nuanced evaluation of the purported quantum speedup in this problem. Our analysis establishes a best-case bound for the HHL-QPF complexity, conclusively demonstrating the absence of any PQA in the direct current power flow (DCPF) and fast decoupled load flow (FDLF) problem. Additionally, we establish that for potential PQA to exist it is necessary to consider DCPF-type problems with a very narrow range of condition number values and readout requirements.

This work presents an efficient data-driven method to construct probabilistic voltage envelopes (PVE) using power flow learning in grids with network contingencies. First, a network-aware Gaussian process (GP) termed Vertex-Degree Kernel (VDK-GP), developed in prior work, is used to estimate voltage-power functions for a few network configurations. The paper introduces a novel multi-task vertex degree kernel (MT-VDK) that amalgamates the learned VDK-GPs to determine power flows for unseen networks, with a significant reduction in the computational complexity and hyperparameter requirements compared to alternate approaches. Simulations on the IEEE 30-Bus network demonstrate the retention and transfer of power flow knowledge in both N-1 and N-2 contingency scenarios. The MT-VDK-GP approach achieves over 50% reduction in mean prediction error for novel N-1 contingency network configurations in low training data regimes (50-250 samples) over VDK-GP. Additionally, MT-VDK-GP outperforms a hyper-parameter based transfer learning approach in over 75% of N-2 contingency network structures, even without historical N-2 outage data. The proposed method demonstrates the ability to achieve PVEs using sixteen times fewer power flow solutions compared to Monte-Carlo sampling-based methods., Comment: 10 Pages

We present a general denoising algorithm for performing simultaneous tomography of quantum states and measurement noise. This algorithm allows us to fully characterize state preparation and measurement (SPAM) errors present in any quantum system. Our method is based on the analysis of the properties of the linear operator space induced by unitary operations. Given any quantum system with a noisy measurement apparatus, our method can output the quantum state and the noise matrix of the detector up to a single gauge degree of freedom. We show that this gauge freedom is unavoidable in the general case, but this degeneracy can be generally broken using prior knowledge on the state or noise properties, thus fixing the gauge for several types of state-noise combinations with no assumptions about noise strength. Such combinations include pure quantum states with arbitrarily correlated errors, and arbitrary states with block independent errors. This framework can further use available prior information about the setting to systematically reduce the number of observations and measurements required for state and noise detection. Our method effectively generalizes existing approaches to the problem, and includes as special cases common settings considered in the literature requiring an uncorrelated or invertible noise matrix, or specific probe states., Comment: 35 pages, 2 figures, Gauge transform definition fixed. DOI links fixed

This paper presents a graph-structured Gaussian process (GP) model for data-driven risk assessment of critical voltage constraints. The proposed GP is based on a novel kernel, named the vertex-degree kernel (VDK), that decomposes the voltage-load relationship based on the network graph. To estimate the GP efficiently, we propose a novel active learning scheme that leverages the additive structure of VDK. Further, we prove a probabilistic bound on the error in risk estimation using VDK-GP model that demonstrates that it is statistically comparable to using standard AC power flow (AC-PF), but does not require computing a large number of ACPF solutions. Simulations demonstrate that the proposed VDK-GP achieves more than two fold sample complexity reduction, compared to a generic GP on medium scale 500-Bus and large scale 1354-Bus power systems. Moreover, active learning achieves an impressive reduction of over 15 times in comparison to the time complexity of Monte-Carlo simulations (MCS), and have risk estimation error of order 1E-4 for both 500-Bus and 1354-Bus system, demonstrating its superior efficiency in risk estimation., Comment: 9 pages

Stochastic fluctuations in power injections from distributed energy resources (DERs) combined with load variability can cause constraint violations (e.g., exceeded voltage limits) in electric distribution systems. To monitor grid operations, sensors are placed to measure important quantities such as the voltage magnitudes. In this paper, we consider a sensor placement problem which seeks to identify locations for installing sensors that can capture all possible violations of voltage magnitude limits. We formulate a bilevel optimization problem that minimizes the number of sensors and avoids false sensor alarms in the upper level while ensuring detection of any voltage violations in the lower level. This problem is challenging due to the nonlinearity of the power flow equations and the presence of binary variables. Accordingly, we employ recently developed conservative linear approximations of the power flow equations that overestimate or underestimate the voltage magnitudes. By replacing the nonlinear power flow equations with conservative linear approximations, we can ensure that the resulting sensor locations and thresholds are sufficient to identify any constraint violations. Additionally, we apply various problem reformulations to significantly improve computational tractability while simultaneously ensuring an appropriate placement of sensors. Lastly, we improve the quality of the results via an approximate gradient descent method that adjusts the sensor thresholds. We demonstrate the effectiveness of our proposed method for several test cases, including a system with multiple switching configurations.

Over the past decade, the usefulness of quantum annealing hardware for combinatorial optimization has been the subject of much debate. Thus far, experimental benchmarking studies have indicated that quantum annealing hardware does not provide an irrefutable performance gain over state-of-the-art optimization methods. However, as this hardware continues to evolve, each new iteration brings improved performance and warrants further benchmarking. To that end, this work conducts an optimization performance assessment of D-Wave Systems' most recent Advantage Performance Update computer, which can natively solve sparse unconstrained quadratic optimization problems with over 5,000 binary decision variables and 40,000 quadratic terms. We demonstrate that classes of contrived problems exist where this quantum annealer can provide run time benefits over a collection of established classical solution methods that represent the current state-of-the-art for benchmarking quantum annealing hardware. Although this work does not present strong evidence of an irrefutable performance benefit for this emerging optimization technology, it does exhibit encouraging progress, signaling the potential impacts on practical optimization tasks in the future.

A prominent challenge to the safe and optimal operation of the modern power grid arises due to growing uncertainties in loads and renewables. Stochastic optimal power flow (SOPF) formulations provide a mechanism to handle these uncertainties by computing dispatch decisions and control policies that maintain feasibility under uncertainty. Most SOPF formulations consider simple control policies such as affine policies that are mathematically simple and resemble many policies used in current practice. Motivated by the efficacy of machine learning (ML) algorithms and the potential benefits of general control policies for cost and constraint enforcement, we put forth a deep neural network (DNN)-based policy that predicts the generator dispatch decisions in real time in response to uncertainty. The weights of the DNN are learnt using stochastic primal-dual updates that solve the SOPF without the need for prior generation of training labels and can explicitly account for the feasibility constraints in the SOPF. The advantages of the DNN policy over simpler policies and their efficacy in enforcing safety limits and producing near optimal solutions are demonstrated in the context of a chance constrained formulation on a number of test cases.

The usual setting for learning the structure and parameters of a graphical model assumes the availability of independent samples produced from the corresponding multivariate probability distribution. However, for many models the mixing time of the respective Markov chain can be very large and i.i.d. samples may not be obtained. We study the problem of reconstructing binary graphical models from correlated samples produced by a dynamical process, which is natural in many applications. We analyze the sample complexity of two estimators that are based on the interaction screening objective and the conditional likelihood loss. We observe that for samples coming from a dynamical process far from equilibrium, the sample complexity reduces exponentially compared to a dynamical process that mixes quickly., Comment: Accepted to ICML 2021

We address the problem of learning of continuous exponential family distributions with unbounded support. While a lot of progress has been made on learning of Gaussian graphical models, we still lack scalable algorithms for reconstructing general continuous exponential families modeling higher-order moments of the data beyond the mean and the covariance. Here, we introduce a computationally efficient method for learning continuous graphical models based on the Interaction Screening approach. Through a series of numerical experiments, we show that our estimator maintains similar requirements in terms of accuracy and sample complexity scalings compared to alternative approaches such as maximization of conditional likelihood, while considerably improving upon the algorithm's run-time., Comment: 24 pages, 11 figures

We examine the problem of optimal transport capacity expansion planning for a gas pipeline network to service the growing demand of gas-fired power plants that are increasingly used to provide base load, flexibility, and reserve generation for bulk electric system. The aim is to determine the minimal cost set of additional pipes and gas compressors that can be added to the network to provide the additional capacity to service future loads. This combinatorial optimization problem is initially formulated as a mixed-integer nonlinear program, which we then extend to account for the variability that is inherent to the demands of gas-fired electricity production and uncertainty in expected future loads. We consider here steady-state flow modeling while ensuring that the solution is feasible for all possible values of interval uncertainty in loads, which results in a challenging semi-infinite problem. We apply previously derived monotonicity properties that enable simplification of the problem to require constraint satisfaction in the two extremal scenarios only, and then formulate the robust gas pipeline network expansion planning problem using a mixed-integer second order cone formulation. We consider case studies on the Belgian network test case to examine the performance of the proposed approach., Comment: 8 pages

We derive conditions for monotonicity properties that characterize general flows of a commodity over a network, where the flow is described by potential and flow dynamics on the edges, as well as potential continuity and Kirchhoff-Neumann mass balance requirements at nodes. The transported commodity may be injected or withdrawn at any of the network nodes, and its movement throughout the network is controlled by nodal actuators. For a class of dissipative nonlinear parabolic partial differential equation (PDE) systems on networks, we derive conditions for monotonicity properties in steady-state flow, as well as for propagation of monotone ordering of states with respect to time-varying boundary condition parameters. In the latter case, initial conditions, as well as time-varying parameters in the coupling conditions at vertices, provide an initial boundary value problem (IBVP). We prove that ordering properties of the solution to the IBVP are preserved when the initial conditions and the parameters of the time-varying coupling law are appropriately ordered. Then, we prove that when monotone ordering is not preserved, the first crossing of solutions occurs at a network node. We consider the implications for robust optimization and optimal control formulations and real-time monitoring of uncertain dynamic flows on networks, and discuss application to subsonic compressible fluid flow with energy dissipation on physical networks. The main result and monitoring policy are demonstrated for gas pipeline test networks and a case study using data corresponding to a real working system. We propose applications of this general result to the control and monitoring of natural gas transmission networks., Comment: arXiv admin note: text overlap with arXiv:1601.05102

In many parts of the world, electric power systems have seen a significant shift towards generation from renewable energy and natural gas. Because of their ability to flexibly adjust power generation in real time, gas-fired power plants are frequently seen as the perfect partner for variable renewable generation. However, this reliance on gas generation increases interdependence and propagates uncertainty between power grids and gas pipelines, and brings coordination and uncertainty management challenges. To address these issues, we propose an uncertainty management framework for uncertain, but bounded gas consumption by gas-fired power plants. The admissible ranges are computed based on a joint optimization problem for the combined gas and electricity networks, which involves chance-constrained scheduling for the electric grid and a novel robust optimization formulation for the natural gas network. This formulation ensures feasibility of the integrated system with a high probability, while providing a tractable numerical formulation. A key advance with respect to existing methods is that our method is based on a physically accurate, validated model for transient gas pipeline flows. Our case study benchmarks our proposed formulation against methods that ignore how reserve activation impacts the fuel use of gas power plants, and only consider predetermined gas consumption. The results demonstrate the importance of considering uncertainty to avoid operating constraint violations and curtailment of gas to the generators.

Graphical models are widely used in science to represent joint probability distributions with an underlying conditional dependence structure. The inverse problem of learning a discrete graphical model given i.i.d samples from its joint distribution can be solved with near-optimal sample complexity using a convex optimization method known as Generalized Regularized Interaction Screening Estimator (GRISE). But the computational cost of GRISE becomes prohibitive when the energy function of the true graphical model has higher-order terms. We introduce NeurISE, a neural net based algorithm for graphical model learning, to tackle this limitation of GRISE. We use neural nets as function approximators in an Interaction Screening objective function. The optimization of this objective then produces a neural-net representation for the conditionals of the graphical model. NeurISE algorithm is seen to be a better alternative to GRISE when the energy function of the true model has a high order with a high degree of symmetry. In these cases NeurISE is able to find the correct parsimonious representation for the conditionals without being fed any prior information about the true model. NeurISE can also be used to learn the underlying structure of the true model with some simple modifications to its training procedure. In addition, we also show a variant of NeurISE that can be used to learn a neural net representation for the full energy function of the true model., Comment: To be published in Advances in Neural Information Processing Systems 33

Estimating the structure of physical flow networks such as power grids is critical to secure delivery of energy. This paper discusses statistical structure estimation in power grids in the "under-excited" regime, where a subset of internal nodes do not have external injection. Prior estimation algorithms based on nodal potentials or voltages fail in the under-excited regime. We propose a novel topology learning algorithm for learning underexcited general (non-radial) networks based on physics-informed conservation laws. We prove the asymptotic correctness of our algorithm for grids with non-adjacent under-excited internal nodes. More importantly, we theoretically analyze our algorithm's efficacy under noisy measurements, and determine bounds on maximum noise under which asymptotically correct recovery is guaranteed. Our approach is validated through simulations with non-linear voltage samples generated on test grids with real injection data, Comment: 10 pages, 8 figures

There is an emerging need for efficient solutions to stochastic AC Optimal Power Flow ({AC-}OPF) to ensure optimal and reliable grid operations in the presence of increasing demand and generation uncertainty. This paper presents a highly scalable data-driven algorithm for stochastic AC-OPF that has extremely low sample requirement. The novelty behind the algorithm's performance involves an iterative scenario design approach that merges information regarding constraint violations in the system with data-driven sparse regression. Compared to conventional methods with random scenario sampling, our approach is able to provide feasible operating points for realistic systems with much lower sample requirements. Furthermore, multiple sub-tasks in our approach can be easily paralleled and based on historical data to enhance its performance and application. We demonstrate the computational improvements of our approach through simulations on different test cases in the IEEE PES PGLib-OPF benchmark library., Comment: a version of this paper will appear in the proceedings of the 21st Power Systems Computation Conference (PSCC 2020)

Growing uncertainty from renewable energy integration and distributed energy resources motivate the need for advanced tools to quantify the effect of uncertainty and assess the risks it poses to secure system operation. Polynomial chaos expansion (PCE) has been recently proposed as a tool for uncertainty quantification in power systems. The method produces results that are highly accurate, but has proved to be computationally challenging to scale to large systems. We propose a modified algorithm based on PCE with significantly improved computational efficiency that retains the desired high level of accuracy of the standard PCE. Our method uses computational enhancements by exploiting the sparsity structure and algebraic properties of the power flow equations. We show the scalability of the method on the 1354 pegase test system, assess the quality of the uncertainty quantification in terms of accuracy and robustness, and demonstrate an example application to solving the chance constrained optimal power flow problem.

This paper presents novel formulations and algorithms for $N$-$k$ interdiction problem in transmission networks. In particular, it formulates spatial and topological resource constraints on attackers for $N$-$k$ interdiction problems and illustrates the formulation with two new classes of $N$-$k$ attacks: (i) Spatial $N$-$k$ attacks where the attack is constrained by geographic distance of a bus chosen by an attacker and (ii) Topological $N$-$k$ attacks where the attack is constrained to connected components. These two specific types of $N$-$k$ attacks compute interdiction plans designed to better model localized attacks, such as those induced by natural disasters or physical attacks. We then formulate these two resource-constrained interdiction problems as bilevel, max-min optimization problems and present a novel constraint generation algorithm to solve these formulations. Detailed case studies analyzing the behavior of spatially and topologically resource-constrained problems and comparing them to the traditional $N$-$k$ interdiction problem are also presented.

The optimal power flow is an optimization problem used in power systems operational planning to maximize economic efficiency while satisfying demand and maintaining safety margins. Due to uncertainty and variability in renewable energy generation and demand, the optimal solution needs to be updated in response to observed uncertainty realizations or near real-time forecast updates. To address the challenge of computing such frequent real-time updates to the optimal solution, recent literature has proposed the use of machine learning to learn the mapping between the uncertainty realization and the optimal solution. Further, learning the active set of constraints at optimality, as opposed to directly learning the optimal solution, has been shown to significantly simplify the machine learning task, and the learnt model can be used to predict optimal solutions in real-time. In this paper, we propose the use of classification algorithms to learn the mapping between the uncertainty realization and the active set of constraints at optimality, thus further enhancing the computational efficiency of the real-time prediction. We employ neural net classifiers for this task and demonstrate the excellent performance of this approach on a number of systems in the IEEE PES PGLib-OPF benchmark library.

Graphical models are useful tools for describing structured high-dimensional probability distributions. Development of efficient algorithms for learning graphical models with least amount of data remains an active research topic. Reconstruction of graphical models that describe the statistics of discrete variables is a particularly challenging problem, for which the maximum likelihood approach is intractable. In this work, we provide the first sample-efficient method based on the Interaction Screening framework that allows one to provably learn fully general discrete factor models with node-specific discrete alphabets and multi-body interactions, specified in an arbitrary basis. We identify a single condition related to model parametrization that leads to rigorous guarantees on the recovery of model structure and parameters in any error norm, and is readily verifiable for a large class of models. Importantly, our bounds make explicit distinction between parameters that are proper to the model and priors used as an input to the algorithm. Finally, we show that the Interaction Screening framework includes all models previously considered in the literature as special cases, and for which our analysis shows a systematic improvement in sample complexity., Comment: Accepted to Advances in Neural Information Processing Systems 33 (NeurIPS 2020), see https://proceedings.neurips.cc/paper/2020/hash/9d702ffd99ad9c70ac37e506facc8c38-Abstract.html

This article develops a strengthened convex quadratic convex (QC) relaxation of the AC Optimal Power Flow (AC-OPF) problem and presents an optimization-based bound-tightening (OBBT) algorithm to compute tight, feasible bounds on the voltage magnitude variables for each bus and the phase angle difference variables for each branch in the network. Theoretical properties of the strengthened QC relaxation that show its dominance over the other variants of the QC relaxation studied in the literature are also derived. The effectiveness of the strengthened QC relaxation is corroborated via extensive numerical results on benchmark AC-OPF test networks. In particular, the results demonstrate that the proposed relaxation consistently provides the tightest variable bounds and optimality gaps with negligible impacts on runtime performance.

Many engineered systems, such as energy and transportation infrastructures, are networks governed by non-linear physical laws. A primary challenge for operators of these networks is to achieve optimal utilization while maintaining safety and feasibility, especially in the face of uncertainty regarding the system model. To address this problem, we formulate a Chance Constrained Optimal Physical Network Flow (CC-OPNF) problem that attempts to optimize the system while satisfying safety limits with a high probability. However, the non-linear equality constraints representing the network physics introduce modelling and optimization challenges which make the chance constraints numerically intractable in their original form. The main contribution of the paper is to present a method to obtain tractable polynomial approximations to the chance constraints using Semidefinite Programming (SDP). The method uses a combination of existing semi-algebraic techniques for projection and volume computation in combination with novel set manipulations to provide conservative inner approximations to the chance constraints. In addition, we develop a new two-step procedure to improve computational speed. While the method is applicable to general physical network flow problems with polynomial constraints, we use the AC optimal power flow problem for electric grids as an example to demonstrate the method numerically.

In many engineered systems, optimization is used for decision making at time-scales ranging from real-time operation to long-term planning. This process often involves solving similar optimization problems over and over again with slightly modified input parameters, often under tight latency requirements. We consider the problem of using the information available through this repeated solution process to directly learn a model of the optimal solution as a function of the input parameters, thus reducing the need to solve computationally expensive large-scale parametric programs in real time. Our proposed method is based on learning relevant sets of active constraints, from which the optimal solution can be obtained efficiently. Using active sets as features preserves information about the physics of the system, enables interpretable models, accounts for relevant safety constraints, and is easy to represent and encode. However, the total number of active sets is also very large, as it grows exponentially with system size. The key contribution of this paper is a streaming algorithm that learns the relevant active sets from training samples consisting of the input parameters and the corresponding optimal solution, without any assumptions on the problem structure. The algorithm comes with theoretical performance guarantees, and is known to converge fast for problem instances with a small number of relevant active sets. It can thus be used to establish the practicability of the learning method. Through extensive experiments on the Optimal Power Flow problem, we observe that often only a few active sets are relevant in practice, suggesting that the active sets is the appropriate level of abstraction for a learning algorithm to target.

The optimal power flow problem plays an important role in the market clearing and operation of electric power systems. However, with increasing uncertainty from renewable energy operation, the optimal operating point of the system changes more significantly in real-time. In this paper, we aim at developing control policies that are able to track the optimal set-point with high probability. The approach is based on the observation that the OPF solution corresponding to a certain uncertainty realization is a basic feasible solution, which provides an affine control policy. The optimality of this basis policy is restricted to uncertainty realizations that share the same set of active constraints. We propose an ensemble control policy that combines several basis policies to improve performance. Although the number of possible bases is exponential in the size of the system, we show that only a few of them are relevant to system operation. We adopt a statistical learning approach to learn these important bases, and provide theoretical results that validate our observations. For most systems, we observe that efficient ensemble policies constructed using as few as ten bases, are able to obtain optimal solutions with high probability.

This paper outlines an optimization framework for choosing fast and reliable control actions in a transmission grid emergency situation. We consider contractual load shedding and generation re-dispatch as exemplary emergency actions. To achieve computational efficiency and scalability, this novel formulation of the robust corrective action optimization is stated in terms of voltages and currents, as opposed to standard formulation in terms of power flows and voltages. The current-voltage formulation is natural for expressing voltage and thermal transmission line constraints, and its major advantage is in the linearity of the power flow equations. The complexity of the current-voltage formulation, which is mainly related to the transformation of voltages and currents into active and reactive power injections, can be largely avoided by stating the cost function directly in terms of currents and using linearized or robust estimates for load and generation constraints. The paper considers five different optimization problem formulations, including the full current-voltage formulation, as well as two convex and two linear approximation to the problem. In a case study on an illustrative case study for the IEEE RTS96 system, we demonstrate pros and cons of the different formulations based on simulations for both normal and contingency operation.

As renewable wind energy penetration rates continue to increase, one of the major challenges facing grid operators is the question of how to control transmission grids in a reliable and a cost-efficient manner. The stochastic nature of wind forces an alteration of traditional methods for solving day-ahead and look-ahead unit commitment and dispatch. In particular, the variability of wind generation increases the risk of unexpected overloads and cascading events. To address these questions, we present an N-1 Security and Chance-Constrained Unit Commitment (SCCUC) that includes models of generation reserves that respond to wind fluctuations and component outages. We formulate the SCCUC as a mixed-integer, second-order cone problem that limits the probability of failure. We develop a modified Benders decomposition algorithm to solve the problem to optimality and present detailed case studies on the IEEE RTS-96 three-area and the IEEE 300 NESTA test systems. The case studies assess the economic impacts of contingencies and various degrees of wind power penetration and demonstrate the effectiveness and scalability of the algorithm., Comment: 24 pages, figures. arXiv admin note: substantial text overlap with arXiv:1602.00079

What is the optimal number of independent observations from which a sparse Gaussian Graphical Model can be correctly recovered? Information-theoretic arguments provide a lower bound on the minimum number of samples necessary to perfectly identify the support of any multivariate normal distribution as a function of model parameters. For a model defined on a sparse graph with $p$ nodes, a maximum degree $d$ and minimum normalized edge strength $\kappa$, this necessary number of samples scales at least as $d \log p/\kappa^2$. The sample complexity requirements of existing methods for perfect graph reconstruction exhibit dependency on additional parameters that do not enter in the lower bound. The question of whether the lower bound is tight and achievable by a polynomial time algorithm remains open. In this paper, we constructively answer this question and propose an algorithm, termed DICE, whose sample complexity matches the information-theoretic lower bound up to a universal constant factor. We also propose a related algorithm SLICE that has a slightly higher sample complexity, but can be implemented as a mixed integer quadratic program which makes it attractive in practice. Importantly, SLICE retains a critical advantage of DICE in that its sample complexity only depends on quantities present in the information theoretic lower bound. We anticipate that this result will stimulate future search of computationally efficient sample-optimal algorithms.

In this manuscript we review new ideas and first results on application of the Graphical Models approach, originated from Statistical Physics, Information Theory, Computer Science and Machine Learning, to optimization problems of network flow type with additional constraints related to the physics of the flow. We illustrate the general concepts on a number of enabling examples from power system and natural gas transmission (continental scale) and distribution (district scale) systems., Comment: 28 pages, 1 figure

Reconstruction of structure and parameters of an Ising model from binary samples is a problem of practical importance in a variety of disciplines, ranging from statistical physics and computational biology to image processing and machine learning. The focus of the research community shifted towards developing universal reconstruction algorithms which are both computationally efficient and require the minimal amount of expensive data. We introduce a new method, Interaction Screening, which accurately estimates the model parameters using local optimization problems. The algorithm provably achieves perfect graph structure recovery with an information-theoretically optimal number of samples, notably in the low-temperature regime which is known to be the hardest for learning. The efficacy of Interaction Screening is assessed through extensive numerical tests on synthetic Ising models of various topologies with different types of interactions, as well as on a real data produced by a D-Wave quantum computer. This study shows that the Interaction Screening method is an exact, tractable and optimal technique universally solving the inverse Ising problem., Comment: 11 pages, 10 pages of supplementary materials

Higher shares of electricity generation from renewable energy sources and market liberalization is increasing uncertainty in power systems operation. At the same time, operation is becoming more flexible with improved control systems and new technology such as phase shifting transformers (PSTs) and high voltage direct current connections (HVDC). Previous studies have shown that the use of corrective control in response to outages contributes to a reduction in operating cost, while maintaining N-1 security. In this work, we propose a method to extend the use of corrective control of PSTs and HVDCs to react to uncertainty. We characterize the uncertainty as continuous random variables, and define the corrective control actions through affine control policies. This allows us to efficiently model control reactions to a large number of uncertainty sources. The control policies are then included in a chance constrained optimal power flow formulation, which guarantees that the system constraints are enforced with a desired probability. By applying an analytical reformulation of the chance constraints, we obtain a second-order cone problem for which we develop an efficient solution algorithm. In a case study for the IEEE 118 bus system, we show that corrective control for uncertainty leads to a decrease in operational cost, while maintaining system security. Further, we demonstrate the scalability of the method by solving the problem for the IEEE 300 bus and the Polish system test cases., Comment: 13 pages

Optimal power flow (OPF) is the central optimization problem in electric power grids. Although solved routinely in the course of power grid operations, it is known to be strongly NP-hard in general, and weakly NP-hard over tree networks. In this paper, we formulate the optimal power flow problem over tree networks as an inference problem over a tree-structured graphical model where the nodal variables are low-dimensional vectors. We adapt the standard dynamic programming algorithm for inference over a tree-structured graphical model to the OPF problem. Combining this with an interval discretization of the nodal variables, we develop an approximation algorithm for the OPF problem. Further, we use techniques from constraint programming (CP) to perform interval computations and adaptive bound propagation to obtain practically efficient algorithms. Compared to previous algorithms that solve OPF with optimality guarantees using convex relaxations, our approach is able to work for arbitrary distribution networks and handle mixed-integer optimization problems. Further, it can be implemented in a distributed message-passing fashion that is scalable and is suitable for "smart grid" applications like control of distributed energy resources. We evaluate our technique numerically on several benchmark networks and show that practical OPF problems can be solved effectively using this approach., Comment: To appear in Proceedings of the 22nd International Conference on Principles and Practice of Constraint Programming (CP 2016(

Many products and innovations become well-known and widely adopted through the social interactions of individuals in a population. The Bass diffusion model has been widely used to model the temporal evolution of adoption in such social systems. In the model, the likelihood of a new adoption is proportional to the number of previous adopters, implicitly assuming a global (or homogeneous) interaction among all individuals in the network. Such global interactions do not exist in many large social networks, however. Instead, individuals typically interact with a small part of the larger population. To quantify the growth rate (or equivalently the adoption timing) in networks with limited interactions, we study a stochastic adoption process where the likelihood that each individual adopts is proportional to the number of adopters among the small group of persons he/she interacts with (and not the entire population of adopters). When the underlying network of interactions is a random $k$-regular graph, we compute the sample path limit of the fraction of adopters. We show the limit coincides with the solution of a differential equation which can viewed as a generalization of the Bass diffusion model. When the degree $k$ is bounded, we show the adoption curve differs significantly from the one corresponds to the Bass diffusion model. In particular, the adoption grows more slowly than what the Bass model projects. In addition, the adoption curve is asymmetric, unlike that of the Bass diffusion model. Such asymmetry has important consequences for the estimation of market potential. Finally, we calculate the timing of early adoptions at finer scales, e.g., logarithmic in the population size.

We consider the problem of learning the underlying graph of an unknown Ising model on p spins from a collection of i.i.d. samples generated from the model. We suggest a new estimator that is computationally efficient and requires a number of samples that is near-optimal with respect to previously established information-theoretic lower-bound. Our statistical estimator has a physical interpretation in terms of "interaction screening". The estimator is consistent and is efficiently implemented using convex optimization. We prove that with appropriate regularization, the estimator recovers the underlying graph using a number of samples that is logarithmic in the system size p and exponential in the maximum coupling-intensity and maximum node-degree., Comment: To be published in Advances in Neural Information Processing Systems 30

We consider the problem of reconstructing a low rank matrix from a subset of its entries and analyze two variants of the so-called Alternating Minimization algorithm, which has been proposed in the past. We establish that when the underlying matrix has rank $r=1$, has positive bounded entries, and the graph $\mathcal{G}$ underlying the revealed entries has bounded degree and diameter which is at most logarithmic in the size of the matrix, both algorithms succeed in reconstructing the matrix approximately in polynomial time starting from an arbitrary initialization. We further provide simulation results which suggest that the second algorithm which is based on the message passing type updates, performs significantly better., Comment: 8 pages, 2 figures

As renewable wind energy penetration rates continue to increase, one of the major challenges facing grid operators is the question of how to control transmission grids in a reliable and a cost-efficient manner. The stochastic nature of wind forces an alteration of traditional methods for solving day-ahead and look-ahead unit commitment and dispatch. In particular, uncontrollable wind generation increases the risk of random component failures. To address these questions, we present an N-1 Security and Chance-Constrained Unit Commitment (SCCUC) that includes the modeling of generation reserves that respond to wind fluctuations and tertiary reserves to account for single component outages. The basic formulation is reformulated as a mixed-integer second-order cone problem to limit the probability of failure. We develop three different algorithms to solve the problem to optimality and present a detailed case study on the IEEE RTS-96 single area system. The case study assesses the economic impacts due to contingencies and various degrees of wind power penetration into the system and also corroborates the effectiveness of the algorithms., Comment: 7 pages, 3 figures

We derive conditions for the propagation of monotone ordering properties for a class of nonlinear parabolic partial differential equation (PDE) systems on metric graphs. For such systems, PDE equations with a general nonlinear dissipation term define evolution on each edge, and balance laws create Kirchhoff-Neumann boundary conditions at the vertices. Initial conditions, as well as time-varying parameters in the coupling conditions at vertices, provide an initial value problem (IVP). We first prove that ordering properties of the solution to the IVP are preserved when the initial conditions and time-varying coupling law parameters at vertices are appropriately ordered. In addition, we prove that when monotone ordering is not preserved, the first crossing of solutions occurs at a graph vertex. We consider the implications for robust optimal control formulations and real-time monitoring involving uncertain dynamic flows on networks, and discuss application to subsonic compressible fluid flow with energy dissipation on physical networks.

Over the past years, the share of electricity production from wind power plants has increased to significant levels in several power systems across Europe and the United States. In order to cope with the fluctuating and partially unpredictable nature of renewable energy sources, transmission system operators (TSOs) have responded by increasing their reserve capacity requirements and by requiring wind power plants to be capable of providing reserves or following active power set-point signals. This paper addresses the issue of efficiently incorporating these new types of wind power control in the day-ahead operational planning. We review the technical requirements the wind power plants must fulfill, and propose a mathematical framework for modeling wind power control. The framework is based on an optimal power flow formulation with weighted chance constraints, which accounts for the uncertainty of wind power forecasts and allows us to limit the risk of constraint violations. In a case study based on the IEEE 118 bus system, we use the developed method to assess the effectiveness of different types of wind power control in terms of operational cost, system security and wind power curtailment., Comment: 7 Pages

We derive a monotonicity property for general, transient flows of a commodity transferred throughout a network, where the flow is characterized by density and mass flux dynamics on the edges with density continuity and mass balance conditions at the nodes. The dynamics on each edge are represented by a general system of partial differential equations that approximates subsonic compressible fluid flow with energy dissipation. The transferred commodity may be injected or withdrawn at any of the nodes, and is propelled throughout the network by nodally located compressors. These compressors are controllable actuators that provide a means to manipulate flows through the network, which we therefore consider as a control system. A canonical problem requires compressor control protocols to be chosen such that time-varying nodal commodity withdrawal profiles are delivered and the density remains within strict limits while an economic or operational cost objective is optimized. In this manuscript, we consider the situation where each nodal commodity withdrawal profile is uncertain, but is bounded within known maximum and minimum time-dependent limits. We introduce the monotone parameterized control system property, and prove that general dynamic dissipative network flows possess this characteristic under certain conditions. This property facilitates very efficient formulation of optimal control problems for such systems in which the solutions must be robust with respect to commodity withdrawal uncertainty. We discuss several applications in which such control problems arise and where monotonicity enables simplified characterization of system behavior.

The development of hydraulic fracturing technology has dramatically increased the supply and lowered the cost of natural gas in the United States, driving an expansion of natural gas-fired generation capacity in several electrical inter-connections. Gas-fired generators have the capability to ramp quickly and are often utilized by grid operators to balance intermittency caused by wind generation. The time-varying output of these generators results in time-varying natural gas consumption rates that impact the pressure and line-pack of the gas network. As gas system operators assume nearly constant gas consumption when estimating pipeline transfer capacity and for planning operations, such fluctuations are a source of risk to their system. Here, we develop a new method to assess this risk. We consider a model of gas networks with consumption modeled through two components: forecasted consumption and small spatio-temporarily varying consumption due to the gas-fired generators being used to balance wind. While the forecasted consumption is globally balanced over longer time scales, the fluctuating consumption causes pressure fluctuations in the gas system to grow diffusively in time with a diffusion rate sensitive to the steady but spatially-inhomogeneous forecasted distribution of mass flow. To motivate our approach, we analyze the effect of fluctuating gas consumption on a model of the Transco gas pipeline that extends from the Gulf of Mexico to the Northeast of the United States., Comment: 10 pages, 7 figures

We consider balanced flows in a natural gas transmission network and discuss computationally hard problems such as establishing if solution of the underlying nonlinear gas flow equations exists, if it is unique, and finding the solution. Particular topologies, e.g. trees, are known to be easy to solve based on a variational description of the gas flow equations, but these approaches do not generalize. In this paper, we show that the gas flow problem can be solved efficiently using the tools of monotone operator theory, provided that we look for solution within certain monotonicity domains. We characterize a family of monotonicity domains, described in terms of Linear Matrix Inequalities (LMI) in the state variables, each containing at most one solution. We also develop an efficient algorithm to choose a particular monotonicity domain, for which the LMI based condition simplifies to a bound on the flows. Performance of the technique is illustrated on exemplary gas networks., Comment: Submitted to CDC 2015