Search

The robustness of neural networks is paramount in safety-critical applications. While most current robustness verification methods assess the worst-case output under the assumption that the input space is known, identifying a verifiable input space $\mathcal{C}$, where no adversarial examples exist, is crucial for effective model selection, robustness evaluation, and the development of reliable control strategies. To address this challenge, we introduce a novel framework, $\texttt{LEVIS}$, comprising $\texttt{LEVIS}$-$\alpha$ and $\texttt{LEVIS}$-$\beta$. $\texttt{LEVIS}$-$\alpha$ locates the largest possible verifiable ball within the central region of $\mathcal{C}$ that intersects at least two boundaries. In contrast, $\texttt{LEVIS}$-$\beta$ integrates multiple verifiable balls to encapsulate the entirety of the verifiable space comprehensively. Our contributions are threefold: (1) We propose $\texttt{LEVIS}$ equipped with three pioneering techniques that identify the maximum verifiable ball and the nearest adversarial point along collinear or orthogonal directions. (2) We offer a theoretical analysis elucidating the properties of the verifiable balls acquired through $\texttt{LEVIS}$-$\alpha$ and $\texttt{LEVIS}$-$\beta$. (3) We validate our methodology across diverse applications, including electrical power flow regression and image classification, showcasing performance enhancements and visualizations of the searching characteristics.

The threat of geomagnetic disturbances (GMDs) to the reliable operation of the bulk energy system has spurred the development of effective strategies for mitigating their impacts. One such approach involves placing transformer neutral blocking devices, which interrupt the path of geomagnetically induced currents (GICs) to limit their impact. The high cost of these devices and the sparsity of transformers that experience high GICs during GMD events, however, calls for a sparse placement strategy that involves high computational cost. To address this challenge, we developed a physics-informed heterogeneous graph neural network (PIHGNN) for solving the graph-based dc-blocker placement problem. Our approach combines a heterogeneous graph neural network (HGNN) with a physics-informed neural network (PINN) to capture the diverse types of nodes and edges in ac/dc networks and incorporates the physical laws of the power grid. We train the PIHGNN model using a surrogate power flow model and validate it using case studies. Results demonstrate that PIHGNN can effectively and efficiently support the deployment of GIC dc-current blockers, ensuring the continued supply of electricity to meet societal demands. Our approach has the potential to contribute to the development of more reliable and resilient power grids capable of withstanding the growing threat that GMDs pose., Comment: Paper is accepted by PSCC 2024

Space weather poses a tremendous threat to power systems: geomagnetic disturbances could result in widespread disruptions and long-duration blackouts, including severe damage to system components. To mitigate their impacts, a handful of strategies exist, with the most promising being the deployment of transformer neutral blocking devices. The high cost of these devices, however, precludes their installation at all substations; this motivates the development of effective solutions for the cost-effective placement of such devices. While the current state-of-the-art in blocker placement methods is insufficient to be applied to real-sized power grids, ongoing research continues to increase the size of networks for which the placement problem remains tractable. Along these lines, the contributions of this paper are two fold: first, a comprehensive overview of the current state-of-the-art in blocker placement methods is provided; and second, a complete optimization formulation - implemented and benchmarked in an open-source software - for the blocker placement problem is presented., Comment: 6 pages. 2 tables

The article introduces the stochastic N-k interdiction problem for power grid operations and planning that aims to identify a subset of k components (out of N components) that maximizes the expected damage, measured in terms of load shed. Uncertainty is modeled through a fixed set of outage scenarios, where each scenario represents a subset of components removed from the grid. We formulate the stochastic N-k interdiction problem as a bi-level optimization problem and propose two algorithmic solutions. The first approach reformulates the bi-level stochastic optimization problem to a single level, mixed-integer linear program (MILP) by dualizing the inner problem and solving the resulting problem directly using a MILP solver to global optimality. The second is a heuristic cutting-plane approach, which is exact under certain assumptions. We compare these approaches in terms of computation time and solution quality using the IEEE-Reliability Test System and present avenues for future research., Comment: 6 pages, 2 figures

This research explores the joint expansion planning of power and water distribution networks, which exhibit interdependence at various levels. We specifically focus on the dependency arising from the power consumption of pumps and develop models to seamlessly integrate new components into existing networks. Subsequently, we formulate the joint expansion planning as a Mixed Integer Nonlinear Program (MINLP). Through the application of this MINLP to a small-scale test network, we demonstrate the advantages of combining expansion planning, including cost savings and reduced redundancy, in comparison to independently expanding power and water distribution networks

We propose a new heuristic approach for solving the challenge of determining optimal placements for geomagnetically induced current blocking devices on electrical grids. Traditionally, these determinations are approached by formulating the problem as mixed-integer nonlinear programming models and solving them using optimization solvers based on the spatial branch-and-bound algorithm.However, computing an optimal solution using the solvers often demands substantial computational time due to their inability to leverage the inherent problem structure. Therefore, in this work we propose a new heuristic approach based on a three-block alternating direction method of multipliers algorithm, and we compare it with an existing stochastic learning algorithm. Both heuristics exploit the structure of the problem of interest. We test these heuristic approaches through extensive numerical experiments conducted on the EPRI-21 and UIUC-150 test systems. The outcomes showcase the superior performance of our methodologies in terms of both solution quality and computational speed when compared with conventional solvers.

This paper focuses on the problem of minimizing the outages due to extreme events on the power grid equitably among all customers of the grid. The paper presents two ways of incorporating fairness into the existing formulations that seek to minimize the total outage in the power grid. The first method is motivated by existing literature on incorporating fairness in optimization problems and this is done by modifying the problem's objective function. The second method introduces a novel notion of fairness, termed $\varepsilon$-fairness, that can be incorporated into existing problem formulations through a single second-order cone constraint. Both these methods are very general and can be used to incorporate fairness in existing planning and operational optimization problems in the power grid and beyond. Extensive computational case studies that examine the effectiveness of both these methods to characterize fairness is presented followed by conclusions and ways forward., Comment: 8 pages

Natural gas ranks second in consumption among primary energy sources in the United States. The majority of production sites are in remote locations, hence natural gas needs to be transported through a pipeline network equipped with a variety of physical components such as compressors, valves, etc. Thus, from the point of view of both economics and reliability, it is desirable to achieve optimal transportation of natural gas using these pipeline networks. The physics that governs the flow of natural gas through various components in a pipeline network is governed by nonlinear and non-convex equality and inequality constraints and the most general steady-flow operations problem takes the form of a Mixed Integer Nonlinear Program. In this paper, we consider one example of steady-flow operations -- the Optimal Gas Flow (OGF) problem for a natural gas pipeline network that minimizes the production cost subject to the physics of steady-flow of natural gas. The ability to quickly determine global optimal solution and a lower bound to the objective value of the OGF for different demand profiles plays a key role in efficient day-to-day operations. One strategy to accomplish this relies on tight relaxations to the nonlinear constraints of the OGF. Currently, many nonlinear constraints that arise due to modeling the non-ideal equation of state either do not have relaxations or have relaxations that scale poorly for realistic network sizes. In this work, we combine recent advancements in the development of polyhedral relaxations for univariate functions to obtain tight relaxations that can be solved within a few seconds on a standard laptop. We demonstrate the quality of these relaxations through extensive numerical experiments on very large scale test networks available in the literature and find that the proposed relaxation is able to prove optimality in 92% of the instances., Comment: 28 pages

As inverter-based generation becomes more common in distribution networks, it is important to create models for use in optimization-based problems that accurately represent their non-linear behavior when saturated. This work presents models for grid-following and grid-forming inverters, and demonstrates their use in optimization-based fault studies. The developed models are shown to provide results in line with experimental tests from literature; however, grid-forming inverter models fail to provide feasible solutions for certain fault types even when currents, voltages, and powers from the models seem reasonable. This work lays down the foundation for the development of relaxed models for both grid-following and grid-forming inverter models for use in optimization problems., Comment: 6 pages. 13 figures

Conventional electric power systems are composed of different unidirectional power flow stages of generation, transmission, and distribution, managed independently by transmission system and distribution system operators. However, as distribution systems increase in complexity due to the integration of distributed energy resources, coordination between transmission and distribution networks will be imperative for the optimal operation of the power grid. However, coupling models and formulations between transmission and distribution is non-trivial, in particular due to the common practice of modeling transmission systems as single-phase, and distribution systems as multi-conductor phase-unbalanced. To enable the rapid prototyping of power flow formulations, in particular in the modeling of the boundary conditions between these two seemingly incompatible data models, we introduce PowerModelsITD.jl, a free, open-source toolkit written in Julia for integrated transmission-distribution (ITD) optimization that leverages mature optimization libraries from the InfrastructureModels.jl-ecosystem. The primary objective of the proposed framework is to provide baseline implementations of steady-state ITD optimization problems, while providing a common platform for the evaluation of emerging formulations and optimization problems. In this work, we introduce the nonlinear formulations currently supported in PowerModelsITD.jl, which include AC-polar, AC-rectangular, current-voltage, and a linear network transportation model. Results are validated using combinations of IEEE transmission and distribution networks.

With the proliferation of distributed generation into distribution networks, the need to consider fault currents in the dispatch problem becomes increasingly relevant. This paper introduces a method for adding fault current constraints into optimal power flow in order to reduce fault currents while minimizing generation cost. The optimal power flow problem is formulated as a single optimization problem with sub-networks representing the faults of interest. Having a single optimization problem allows the decision variables to be coupled across the optimal power flow and the fault current studies without having to iterate over possible solutions. The proposed method is applicable to unbalanced distribution networks, including those with transformers that introduce phase-shifts., Comment: 5 pages. 1 figure. 3 tables

The classic pump scheduling or Optimal Water Flow (OWF) problem for water distribution networks (WDNs) minimizes the cost of power consumption for a given WDN over a fixed time horizon. In its exact form, the OWF is a computationally challenging mixed-integer nonlinear program (MINLP). It is complicated by nonlinear equality constraints that model network physics, discrete variables that model operational controls, and intertemporal constraints that model changes to storage devices. To address the computational challenges of the OWF, this paper develops tight polyhedral relaxations of the original MINLP, derives novel valid inequalities (or cuts) using duality theory, and implements novel optimization-based bound tightening and cut generation procedures. The efficacy of each new method is rigorously evaluated by measuring empirical improvements in OWF primal and dual bounds over forty-five literature instances. The evaluation suggests that our relaxation improvements, model strengthening techniques, and a thoughtfully selected polyhedral relaxation partitioning scheme can substantially improve OWF primal and dual bounds, especially when compared with similar relaxation-based techniques that do not leverage these new methods.

In airborne light detection and ranging (LiDAR) systems, misalignments between the LiDAR-scanner and the inertial navigation system (INS) mounted on an unmanned aerial vehicle (UAV)'s frame can lead to inaccurate 3D point clouds. Determining the orientation offset, or boresight error is key to many LiDAR-based applications. In this work, we introduce a mixed-integer quadratically constrained quadratic program (MIQCQP) that can globally solve this misalignment problem. We also propose a nested spatial branch and bound (nsBB) algorithm that improves computational performance. The nsBB relies on novel preprocessing steps that progressively reduce the problem size. In addition, an adaptive grid search (aGS) allowing us to obtain quick heuristic solutions is presented. Our algorithms are open-source, multi-threaded and multi-machine compatible.

Recent increases in gas-fired power generation have engendered increased interdependencies between natural gas and power transmission systems. These interdependencies have amplified existing vulnerabilities to gas and power grids, where disruptions can require the curtailment of load in one or both systems. Although typically operated independently, coordination of these systems during severe disruptions can allow for targeted delivery to lifeline services, including gas delivery for residential heating and power delivery for critical facilities. To address the challenge of estimating maximum joint network capacities under such disruptions, we consider the task of determining feasible steady-state operating points for severely damaged systems while ensuring the maximal delivery of gas and power loads simultaneously, represented mathematically as the nonconvex joint Maximal Load Delivery (MLD) problem. To increase its tractability, we present a mixed-integer convex relaxation of the MLD problem. Then, to demonstrate the relaxation's effectiveness in determining bounds on network capacities, exact and relaxed MLD formulations are compared across various multi-contingency scenarios on nine joint networks ranging in size from 25 to 1,191 nodes. The relaxation-based methodology is observed to accurately and efficiently estimate the impacts of severe joint network disruptions, often converging to the relaxed MLD problem's globally optimal solution within ten seconds.

Demand response for electrical power networks is a mature field that has yielded numerous efficiency and resilience benefits like managing the peaks and valleys of electricity usage, reduction in peak electricity usage, to name a few. However, only recently has the study of the counterpart to demand response for electric power in natural gas started to receive similar levels of attention. Natural gas systems are increasingly operating at or near capacity, which challenges these systems to meet all the needs for gas, especially during severe winter weather. However, unlike demand response programs in electrical networks, demand response in gas networks cannot shift peak usage. Here, we develop analogues to demand response that can help improve the resilience of natural gas systems by reducing peak consumption and thereby limiting potential disruptions such events can cause. This paper develops a mathematical formulation to support a residential-level demand response analogue for natural gas based on current and anticipated smart thermostat technologies. The mathematical formulation takes the form of an optimal control problem (OCP) that leverages physics constraints to model temperature changes, balance equitable service, and optimize the gas consumption for collections of houses. On test problems, the formulation demonstrates significant benefits, including the ability to cut peak demand by 15% while still ensuring equitable service to customers., Comment: 27 pages

Severe geomagnetic disturbances (GMDs) increase the magnitude of the electric field on the Earth's surface (E-field) and drive geomagnetically-induced currents (GICs) along the transmission lines in electric grids. These additional currents can pose severe risks, such as current distortions, transformer saturation and increased reactive power losses, each of which can lead to system unreliability. Several mitigation actions (e.g., changing grid topology) exist that can reduce the harmful GIC effects on the grids. Making such decisions can be challenging, however, because the magnitude and direction of the E-field are uncertain and non-stationary. In this paper, we model uncertain E-fields using the distributionally robust optimization (DRO) approach that determines optimal transmission grid operations such that the worst-case expectation of the system cost is minimized. We also capture the effect of GICs on the nonlinear AC power flow equations. For solution approaches, we develop an accelerated column-and-constraint generation (CCG) algorithm by exploiting a special structure of the support set of uncertain parameters representing the E-field. Extensive numerical experiments based on "epri-21" and "uiuc-150" systems, designed for GMD studies, demonstrate (i) the computational performance of the accelerated CCG algorithm, (ii) the superior performance of distributionally robust grid operations that satisfy nonlinear, nonconvex AC power flow equations and GIC constraints, in comparison with standard stochastic programming-based methods during the out-of-sample testing., Comment: 11 pages, 7 figures, 9 tables

We formulate a nonlinear optimal control problem for intra-day operation of a natural gas pipeline network that includes storage reservoirs. The dynamics of compressible gas flow through pipes, compressors, reservoirs, and wells are considered. In particular, a reservoir is modeled as a rigid, hollow container that stores gas under isothermal conditions and uniform density, and a well is modeled as a vertical pipe. For each pipe, flow dynamics are described by a coupled partial differential equation (PDE) system in density and mass flux variables, with momentum dissipation modeled using the Darcy-Wiesbach friction approximation. Compressors are modeled as scaling up the pressure of gas between inlet and outlet. The governing equations for all network components are spatially discretized and assembled into a nonlinear differential-algebraic equation (DAE) system, which synthesizes above-ground pipeline and subsurface reservoir dynamics into a single reduced-order model. We seek to maximize an objective function that quantifies economic profit and network efficiency subject to the flow equations and inequalities that represent operating limitations. The problem is solved using a primal-dual interior point solver and the solutions are validated in computational experiments and simulations on several pipeline test networks to demonstrate the effectiveness of the proposed methodology., Comment: 13 pages

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

Geomagnetic disturbances and E3 high-altitude electromagnetic pulse events pose a substantial threat to the electrical grid by adversely impacting and damaging high-voltage transmission networks and equipment. To evaluate the risks and mitigate the potential effects of these hazards, this work proposes PowerModelsGMD.jl (abbr. PMsGMD). PMsGMD is an open-source Julia package that solves for quasi-dc line flow and ac power flow problems in a system subjected to geomagnetically induced currents. Unlike commercially available software solutions, it is extensible and applicable to a variety of problems. The flexibility of this framework is demonstrated by applying it to the problem of identifying mitigation strategies via line switching for a time-extended transformer heating problem. An overview of PMsGMD is presented in this paper: introduction to its design, validation of its implementation, demonstration of its performance and effectiveness, and a description of how it may be applied to aid system-operation decisions., Comment: Technical Report

The majority of overland transport needs for crude petroleum and refined petroleum products are met using pipelines. Numerous studies have developed optimization methods for design of these systems in order to minimize construction costs while meeting capacity requirements. Here, we formulate problems to optimize the operations of existing single liquid commodity pipeline systems subject to physical flow and pump engineering constraints. The objectives are to maximize the economic value created for users of the system and to minimize operating costs. We present a general computational method for this class of continuous, non-convex nonlinear programs, and examine the use of pump operating settings and flow allocations as decision variables. The approach is applied to compute optimal operating regimes and perform engineering economic sensitivity analyses for a case study of a crude oil pipeline developed using publicly available data.

In this paper, we consider the canonical water network design problem, which contains nonconvex potential loss functions and discrete resistance choices with varying costs. Traditionally, to resolve the nonconvexities of this problem, relaxations of the potential loss constraints have been applied to yield a more tractable mixed-integer convex program (MICP). However, design solutions to these relaxed problems may not be feasible with respect to the full nonconvex physics. In this paper, it is shown that, in fact, the original mixed-integer nonconvex program can be reformulated exactly as an MICP. Beginning with a convex program previously used for proving nonlinear network design feasibility, strong duality is invoked to construct a novel, convex primal-dual system embedding all physical constraints. This convex system is then augmented to form an exact MICP formulation of the original design problem. Using this novel MICP as a foundation, a global optimization algorithm is developed, leveraging heuristics, outer approximations, and feasibility cutting planes for infeasible designs. Finally, the algorithm is compared against the previous relaxation-based state of the art in water network design over a number of standard benchmark instances from the literature.

As the use of renewable generation has increased, electric power systems have become increasingly reliant on natural gas-fired power plants as fast ramping sources for meeting fluctuating bulk power demands. This dependence has introduced new vulnerabilities to the power grid, including disruptions to gas transmission networks from natural and man-made disasters. To address the operational challenges arising from these disruptions, we consider the task of determining a feasible steady-state operating point for a damaged gas pipeline network while ensuring the maximal delivery of load. We formulate the mixed-integer nonconvex maximal load delivery (MLD) problem, which proves difficult to solve on large-scale networks. To address this challenge, we present a mixed-integer convex relaxation of the MLD problem and use it to determine bounds on the transport capacity of a gas pipeline system. To demonstrate the effectiveness of the relaxation, the exact and relaxed formulations are compared across a large number of randomized damage scenarios on nine natural gas pipeline network models ranging in size from 11 to 4197 junctions. A proof of concept application, which assumes network damage from a set of synthetically generated earthquakes, is also presented to demonstrate the utility of the proposed optimization-based capacity evaluation in the context of risk assessment for natural disasters. For all but the largest network, the relaxation-based method is found to be suitable for use in evaluating the impacts of multi-contingency network disruptions, often converging to the optimal solution of the relaxed formulation in less than ten seconds., Comment: Corrected alignment of histograms in Figure 2

Geomagnetic disturbances (GMDs), a result of space weather, pose a severe risk to electric grids. When GMDs occur, they can cause geomagnetically-induced currents (GICs), which saturate transformers, induce hot-spot heating, and increase reactive power losses in the transmission grid. Furthermore, uncertainty in the magnitude and orientation of the geo-electric field, and insufficient historical data make the problem of mitigating the effects of uncertain GMDs challenging. In this paper, we propose a novel distributionally robust optimization (DRO) approach that models uncertain GMDs and mitigates the effects of GICs on electric grids. This is achieved via a set of mitigation actions (e.g., line switching, locating blocking devices, generator re-dispatch and load shedding), prior to the GMD event, such that the worst-case expectation of the system cost is minimized. To this end, we develop a column-and-constraint generation algorithm that solves a sequence of mixed-integer second-order conic programs to handle the underlying convex support set of the uncertain GMDs. Also, we present a monolithic exact reformulation of our DRO model when the underlying support set can be approximated by a polytope with three extreme points. Numerical experiments on 'epri-21' system show the efficacy of the proposed algorithms and the exact reformulation of our DRO model.

In this paper, we present a mixed-integer linear programming (MILP) formulation of a piecewise, polyhedral relaxation (PPR) of a multilinear term using its convex hull representation. Based on the solution of the PPR, we also present a MILP formulation whose solutions are feasible for nonconvex, multilinear equations. We then present computational results showing the effectiveness of proposed formulations on instances of standard benchmarks of nonlinear programs (NLPs) with multilinear terms and compare the proposed formulation with a traditional formulation that is built by recursively relaxing bilinear groupings of multilinear terms.

In recent years, there have been increasing concerns about the impacts of geomagnetic disturbances (GMDs) on electrical power systems. Geomagnetically-induced currents (GICs) can saturate transformers, induce hot-spot heating and increase reactive power losses. Unpredictable GMDs caused by solar storms can significantly increase the risk of transformer failure. In this paper, we develop a two-stage, distributionally robust (DR) optimization formulation that models uncertain GMDs and mitigates the effects of GICs on power systems through existing system controls (e.g., line switching, generator re-dispatch, and load shedding). This model assumes an ambiguity set of probability distributions for induced geo-electric fields which capture uncertain magnitudes and orientations of a GMD event. We employ state-of-the-art linear relaxation methods and reformulate the problem as a two-stage DR model. We use this formulation to develop a decomposition framework for solving the problem. We demonstrate the approach on the modified Epri21 system and show that the DR optimization method effectively handles prediction errors of GMD events.

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.

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.

In this paper, we present convex hull formulations for a mixed-integer, multilinear term/function (MIMF) that features products of multiple continuous and binary variables. We develop two equivalent convex relaxations of an MIMF and study their polyhedral properties in their corresponding higher-dimensional spaces. We numerically observe that the proposed formulations consistently perform better than state-of-the-art relaxation approaches.

Power distribution in remote communities often depends on off-grid microgrids. In order to address the reliability challenges for these microgrids, we develop a mathematical model for topology design, capacity planning, and operation of distributed energy resources in microgrids that includes N-1 security analysis. Due to the prohibitive size of the optimization problem, we develop a rolling-horizon algorithm that is combined with scenario-based decomposition to efficiently solve the model. We demonstrate the efficiency of our algorithm on an adapted IEEE test network and a real network from an Alaskan microgrid. We also compare our model's required solution time with commercial solvers and recently developed decomposition algorithms to solve similar problems., Comment: 21 Pages, 9 figures, submitted to Applied Energy

In recent years, microgrids, i.e., disconnected distribution systems, have received increasing interest from power system utilities to support the economic and resiliency posture of their systems. The economics of long distance transmission lines prevent many remote communities from connecting to bulk transmission systems and these communities rely on off-grid microgrid technology. Furthermore, communities that are connected to the bulk transmission system are investigating microgrid technologies that will support their ability to disconnect and operate independently during extreme events. In each of these cases, it is important to develop methodologies that support the capability to design and operate microgrids in the absence of transmission over long periods of time. Unfortunately, such planning problems tend to be computationally difficult to solve and those that are straightforward to solve often lack the modeling fidelity that inspires confidence in the results. To address these issues, we first develop a high fidelity model for design and operations of a microgrid that include component efficiencies, component operating limits, battery modeling, unit commitment, capacity expansion, and power flow physics; the resulting model is a mixed-integer quadratically-constrained quadratic program (MIQCQP). We then develop an iterative algorithm, referred to as the Model Predictive Control (MPC) algorithm, that allows us to solve the resulting MIQCQP. We show, through extensive computational experiments, that the MPC-based method can scale to problems that have a very long planning horizon and provide high quality solutions that lie within 5\% of optimal., Comment: To appear in "Power Systems Computation Conference", Dublin, Ireland

Since the alternating current optimal power flow (ACOPF) problem was introduced in 1962, developing efficient solution algorithms for the problem has been an active field of research. In recent years, there has been increasing interest in convex relaxations-based solution approaches that are often tight in practice. Based on these approaches, we develop tight piecewise convex relaxations with convex-hull representations, an adaptive, multivariate partitioning algorithm with bound tightening that progressively improves these relaxations and, given sufficient time, converges to the globally optimal solution. We illustrate the strengths of our algorithm using benchmark ACOPF test cases from the literature. Computational results show that our novel algorithm reduces the best-known optimality gaps for some hard ACOPF cases.

The dynamics of flooding are primarily influenced by the shape, height, and roughness (friction) of the underlying topography. For this reason, mechanisms to mitigate floods frequently employ structural measures that either modify topographic elevation, e.g., through the placement of levees and sandbags, or increase roughness, e.g., through revegetation projects. However, the configuration of these measures is typically decided in an ad hoc manner, limiting their overall effectiveness. The advent of high-performance surface water modeling software and improvements in black-box optimization suggest that a more principled design methodology may be possible. This paper proposes a new computational approach to the problem of designing structural mitigation strategies under physical and budgetary constraints. It presents the development of a problem discretization amenable to simulation-based, derivative-free optimization. However, meta-heuristics alone are found to be insufficient for obtaining quality solutions in a reasonable amount of time. As a result, this paper proposes novel numerical and physics-based procedures to improve convergence to a high-quality mitigation. The efficiency of the approach is demonstrated on hypothetical dam break scenarios of varying complexity under various mitigation budget constraints. In particular, experimental results show that, on average, the final proposed algorithm results in a 65% improvement in solution quality compared to a direct implementation.

Distributed generation and remotely controlled switches have emerged as important technologies to improve the resiliency of distribution grids against extreme weather-related disturbances. Therefore it becomes impor- tant to study how best to place them on the grid in order to meet a resiliency criteria, while minimizing costs and capturing their dependencies on the associated communication systems that sustains their distributed operations. This paper introduces the Optimal Resilient Design Problem for Distribution and Communi- cation Systems (ORDPDC) to address this need. The ORDPDC is formulated as a two-stage stochastic mixed-integer program that captures the physical laws of distribution systems, the communication connec- tivity of the smart grid components, and a set of scenarios which specifies which components are affected by potential disasters. The paper proposes an exact branch-and-price algorithm for the ORDPDC which features a strong lower bound and a variety of acceleration schemes to address degeneracy. The ORDPDC model and branch-and-price algorithm were evaluated on a variety of test cases with varying disaster inten- sities and network topologies. The results demonstrate the significant impact of the network topologies on the expansion plans and costs, as well as the computational benefits of the proposed approach.

In recent years, the power system research community has seen an explosion of novel methods for formulating and solving power network optimization problems. These emerging methods range from new power flow approximations, which go beyond the traditional DC power flow by capturing reactive power, to convex relaxations, which provide solution quality and runtime performance guarantees. Unfortunately, the sophistication of these emerging methods often presents a significant barrier to evaluating them on a wide variety of power system optimization applications. To address this issue, this work proposes PowerModels, an open-source platform for comparing power flow formulations. From its inception, PowerModels was designed to streamline the process of evaluating different power flow formulations on shared optimization problem specifications. This work provides a brief introduction to the design of PowerModels, validates its implementation, and demonstrates its effectiveness with a proof-of-concept study analyzing five different formulations of the Optimal Power Flow problem.

This work considers the task of finding an AC-feasible operating point of a severely damaged transmission network while ensuring that a maximal amount of active power loads can be delivered. This AC Maximal Load Delivery (AC-MLD) task is a nonconvex nonlinear optimization problem that is incredibly challenging to solve on large-scale transmission system datasets. This work demonstrates that convex relaxations of the AC-MLD problem provide a reliable and scalable method for finding high-quality bounds on the amount of active power that can be delivered in the AC-MLD problem. To demonstrate their effectiveness, the solution methods proposed in this work are rigorously evaluated on 1000 N-k scenarios on seven power networks ranging in size from 70 to 6000 buses. The most effective relaxation of the AC-MLD problem converges in less than 20 seconds on commodity computing hardware for all 7000 of the scenarios considered., Comment: The problem considered in this work is also known as AC Minimal Load-Shedding

In this work, we develop an adaptive, multivariate partitioning algorithm for solving mixed-integer nonlinear programs (MINLP) with multi-linear terms to global optimality. This iterative algorithm primarily exploits the advantages of piecewise polyhedral relaxation approaches via disjunctive formulations to solve MINLPs to global optimality in contrast to the conventional spatial branch-and-bound approaches. In order to maintain relatively small-scale mixed-integer linear programs at every iteration of the algorithm, we adaptively partition the variable domains appearing in the multi-linear terms. We also provide proofs on convergence guarantees of the proposed algorithm to a global solution. Further, we discuss a few algorithmic enhancements based on the sequential bound-tightening procedure as a presolve step, where we observe the importance of solving piecewise relaxations compared to basic convex relaxations to speed-up the convergence of the algorithm to global optimality. We demonstrate the effectiveness of our disjunctive formulations and the algorithm on well-known benchmark problems (including Pooling and Blending instances) from MINLPLib and compare with state-of-the-art global optimization solvers. With this novel approach, we solve several large-scale instances which are, in some cases, intractable by the global optimization solver. We also shrink the best known optimality gap for one of the hard, generalized pooling problem instance.

The recent emergence of novel computational devices, such as adiabatic quantum computers, CMOS annealers, and optical parametric oscillators, present new opportunities for hybrid-optimization algorithms that are hardware accelerated by these devices. In this work, we propose the idea of an Ising processing unit as a computational abstraction for reasoning about these emerging devices. The challenges involved in using and benchmarking these devices are presented and commercial mixed integer programming solvers are proposed as a valuable tool for the validation of these disparate hardware platforms. The proposed validation methodology is demonstrated on a D-Wave 2X adiabatic quantum computer, one example of an Ising processing unit. The computational results demonstrate that the D-Wave hardware consistently produces high-quality solutions and suggests that as IPU technology matures it could become a valuable co-processor in hybrid-optimization algorithms.

In the electrical grid, the distribution system is themost vulnerable to severe weather events. Well-placed and coordinatedupgrades, such as the combination of microgrids, systemhardening and additional line redundancy, can greatly reduce thenumber of electrical outages during extreme events. Indeed, ithas been suggested that resilience is one of the primary benefitsof networked microgrids. We formulate a resilient distributiongrid design problem as a two-stage stochastic program andmake use of decomposition-based heuristic algorithms to scaleto problems of practical size. We demonstrate the feasibilityof a resilient distribution design tool on a model of an actualdistribution network. We vary the study parameters, i.e., thecapital cost of microgrid generation relative to system hardeningand target system resilience metrics, and find regions in thisparametric space corresponding to different distribution systemarchitectures, such as individual microgrids, hardened networks,and a transition region that suggests the benefits of microgridsnetworked via hardened circuit segments.

This paper considers a probabilistic generalization of the $N$-$k$ failure-identification problem in power transmission networks, where the probability of failure of each component in the network is known a priori and the goal of the problem is to find a set of $k$ components that maximizes disruption to the system loads weighted by the probability of simultaneous failure of the $k$ components. The resulting problem is formulated as a bilevel mixed-integer nonlinear program. Convex relaxations, linear approximations, and heuristics are developed to obtain feasible solutions that are close to the optimum. A general cutting-plane algorithm is proposed to solve the convex relaxation and linear approximations of the $N$-$k$ problem. Extensive numerical results corroborate the effectiveness of the proposed algorithms on small-, medium-, and large-scale test instances, the test instances include the IEEE 14-bus system, the IEEE single-area and three-area RTS96 systems, the IEEE 118-bus system, the WECC 240-bus test system, the 1354-bus PEGASE system, and the 2383-bus Polish winter-peak test system., Comment: 17 pages, Networks, 2018

As illustrated in recent years (Superstorm Sandy, the Northeast Ice Storm of 1998, etc.), extreme weather events pose an enormous threat to the electric power transmission systems and the associated socio-economic systems that depend on reliable delivery of electric power. Besides inevitable malfunction of power grid components, deliberate malicious attacks can cause high risks to the service. These threats motivate the need for approaches and methods that improve the resilience of power systems. In this paper, we develop a model and tractable methods for optimizing the upgrade of transmission systems through a combination of hardening existing components, adding redundant lines, switches, generators, and FACTS and phase-shifting devices. While many of these controllable components are included in traditional design (expansion planning) problems, we uniquely assess their benefits from a resiliency point of view. More importantly, perhaps, we evaluate the suitability of using state-of-the-art AC power flow relaxations versus the common DC approximation in resilience improvement studies. The resiliency model and algorithms are tested on a modified version of the RTS-96 (single area) system.

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

In recent years, there have been increasing concerns about how geomagnetic disturbances (GMDs) impact electrical power systems. Geomagnetically-induced currents (GICs) can saturate transformers, induce hot spot heating and increase reactive power losses. These effects can potentially cause catastrophic damage to transformers and severely impact the ability of a power system to deliver power. To address this problem, we develop a model of GIC impacts to power systems that includes 1) GIC thermal capacity of transformers as a function of normal Alternating Current (AC) and 2) reactive power losses as a function of GIC. We use this model to derive an optimization problem that protects power systems from GIC impacts through line switching, generator redispatch, and load shedding. We employ state-of-the-art convex relaxations of AC power flow equations to lower bound the objective. We demonstrate the approach on a modified RTS96 system and the UIUC 150-bus system and show that line switching is an effective means to mitigate GIC impacts. We also provide a sensitivity analysis of optimal switching decisions with respect to GMD direction.

Generalizing both mixed-integer linear optimization and convex optimization, mixed-integer convex optimization possesses broad modeling power but has seen relatively few advances in general-purpose solvers in recent years. In this paper, we intend to provide a broadly accessible introduction to our recent work in developing algorithms and software for this problem class. Our approach is based on constructing polyhedral outer approximations of the convex constraints, resulting in a global solution by solving a finite number of mixed-integer linear and continuous convex subproblems. The key advance we present is to strengthen the polyhedral approximations by constructing them in a higher-dimensional space. In order to automate this extended formulation we rely on the algebraic modeling technique of disciplined convex programming (DCP), and for generality and ease of implementation we use conic representations of the convex constraints. Although our framework requires a manual translation of existing models into DCP form, after performing this transformation on the MINLPLIB2 benchmark library we were able to solve a number of unsolved instances and on many other instances achieve superior performance compared with state-of-the-art solvers like Bonmin, SCIP, and Artelys Knitro.

In this work, we propose a two-stage approach to strengthen piecewise McCormick relaxations for mixed-integer nonlinear programs (MINLP) with multi-linear terms. In the first stage, we exploit Constraint Programing (CP) techniques to contract the variable bounds. In the second stage we partition the variables domains using a dynamic multivariate partitioning scheme. Instead of equally partitioning the domains of variables appearing in multi-linear terms, we construct sparser partitions yet tighter relax- ations by iteratively partitioning the variable domains in regions of interest. This approach decouples the number of partitions from the size of the variable domains, leads to a significant reduction in computation time, and limits the number of binary variables that are introduced by the partitioning. We demonstrate the performance of our algorithm on well-known benchmark problems from MINLPLIB and discuss the computational benefits of CP-based bound tightening procedures.

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

The growing reliance of electric power systems on gas-fired generation to balance intermittent sources of renewable energy has increased the variation and volume of flows through natural gas transmission pipelines. Adapting pipeline operations to maintain efficiency and security under these new conditions requires optimization methods that account for transients and that can quickly compute solutions in reaction to generator re-dispatch. This paper presents an efficient scheme to minimize compression costs under dynamic conditions where deliveries to customers are described by time-dependent mass flow. The optimization scheme relies on a compact representation of gas flow physics, a trapezoidal discretization in time and space, and a two-stage approach to minimize energy costs and maximize smoothness. The resulting large-scale nonlinear programs are solved using a modern interior-point method. The proposed optimization scheme is validated against an integration of dynamic equations with adaptive time-stepping, as well as a recently proposed state-of-the-art optimal control method. The comparison shows that the solutions are feasible for the continuous problem and also practical from an operational standpoint. The results also indicate that our scheme provides at least an order of magnitude reduction in computation time relative to the state-of-the-art and scales to large gas transmission networks with more than 6000 kilometers of total pipeline.

We present a unifying framework for generating extended formulations for the polyhedral outer approximations used in algorithms for mixed-integer convex programming (MICP). Extended formulations lead to fewer iterations of outer approximation algorithms and generally faster solution times. First, we observe that all MICP instances from the MINLPLIB2 benchmark library are conic representable with standard symmetric and nonsymmetric cones. Conic reformulations are shown to be effective extended formulations themselves because they encode separability structure. For mixed-integer conic-representable problems, we provide the first outer approximation algorithm with finite-time convergence guarantees, opening a path for the use of conic solvers for continuous relaxations. We then connect the popular modeling framework of disciplined convex programming (DCP) to the existence of extended formulations independent of conic representability. We present evidence that our approach can yield significant gains in practice, with the solution of a number of open instances from the MINLPLIB2 benchmark library., Comment: To be presented at IPCO 2016

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

Modern society critically depends on the services electric power provides. Power systems rely on a network of power lines and transformers to deliver power from sources of power (generators) to the consumers (loads). However, when power lines fail (for example, through lightning or natural disasters) or when the system is heavily used, the network is often unable to fulfill all of the demand for power. While systems are vulnerable to these failures, increasingly, sophisticated control devices are being deployed to improve the efficiency of power systems. Such devices can also be used to improve the resiliency of power systems to failures. In this paper, we focus on using FACTS devices in this context. A FACTS device allows power grid operators to adjust the impedance parameters of power lines, thereby redistributing flow in the network and potentially increasing the amount of power that is supplied. Here we develop new approaches for determining the optimal parameter settings for FACTS devices in order to supply the maximal amount of power when networks are stressed, e.g. power line failures and heavy utilization.

Expansion of natural gas networks is a critical process involving substantial capital expenditures with complex decision-support requirements. Given the non-convex nature of gas transmission constraints, global optimality and infeasibility guarantees can only be offered by global optimisation approaches. Unfortunately, state-of-the-art global optimisation solvers are unable to scale up to real-world size instances. In this study, we present a convex mixed-integer second-order cone relaxation for the gas expansion planning problem under steady-state conditions. The underlying model offers tight lower bounds with high computational efficiency. In addition, the optimal solution of the relaxation can often be used to derive high-quality solutions to the original problem, leading to provably tight optimality gaps and, in some cases, global optimal soluutions. The convex relaxation is based on a few key ideas, including the introduction of flux direction variables, exact McCormick relaxations, on/off constraints, and integer cuts. Numerical experiments are conducted on the traditional Belgian gas network, as well as other real larger networks. The results demonstrate both the accuracy and computational speed of the relaxation and its ability to produce high-quality solutions.