Search

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. [ABSTRACT FROM AUTHOR]

An increasing dependence on natural gas has amplified existing 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 problem of estimating the steady-state operating capacity of a damaged gas pipeline network while ensuring the maximal delivery of load. Specifically, 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 relaxation of the MLD problem and use it to determine bounds on the transport capacity of a gas pipeline system. A rigorous computational evaluation over network models ranging in size from 11 to 4 , 197 junctions shows that the relaxation-based method is suitable for analyzing the impacts of multi-contingency network disruptions, often converging to the optimal solution of the relaxation in less than ten seconds. • Maximal Load Delivery (MLD) analysis estimates the capacity of a damaged gas system. • Relaxations of gas network physics increase the tractability of an MLD analysis. • Rigorous benchmarking illustrates computational advantages of the relaxations. • MLD analyses can help estimate the effects of natural disasters on gas networks. [ABSTRACT FROM AUTHOR]

We propose machine learning-based (ML) methods to accelerate convergence to global solutions for the AC Optimal Power Flow (AC-OPF) problem. In particular, for the non-convex AC-OPF problem, optimality-based bound tightening (OBBT) has been observed to be a very effective approach for tightening the variable domains, thus leading to tight convex relaxations that are nearly global optimum solutions. However, by construction, OBBT is computationally expensive even on medium-scaled power networks. To address this issue, we propose a novel ML-based policy to replace the exhaustive algorithm of OBBT by choosing a subset of variables whose tightening of bounds can still contribute to the best improvement of the convex relaxation of the AC-OPF problem. To this end, we leverage historical data of load profiles for a test system to learn a map between the system loading and subset selection of variables which will need to participate in the OBBT algorithm, thus enabling us to find near-global optimal solutions at faster run-times. Finally, we present detailed numerical studies on a few medium-sized benchmark instances, on which we observe up to 6.3× speed-up in OBBT run times. • Novel ML-based policies to accelerate convergence to global solutions for the AC-OPF problem. • Applying optimality-based bound tightening (OBBT) algorithm on an important variable subset. • Leveraging historical data of load profiles to learn a map between the loads and variable subsets. • Numerical studies for corroborating efficacy of ML-based OBBT algorithm on IEEE instances. [ABSTRACT FROM AUTHOR]

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. • New heuristic approaches for placing geomagnetically induced current blocking devices. • The proposed approaches provide high-quality solutions. • The proposed approaches are scalable with respect to the problem instance size. [ABSTRACT FROM AUTHOR]

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. • AI-powered grid DC blocker against geomagnetic threats. • Physics-informed heterogeneous graph neural networks optimizes blocker placement. • Model ensures effective protection and proves effectiveness from two case studies. [ABSTRACT FROM AUTHOR]

Power grid operators decide where and how much power to generate based on the current topology and demands of the network. The topology can change as safety devices trigger (connecting or disconnecting parts of the network) or as lines go down. Often, the operator cannot observe these events directly, but instead has contemporary measurements and historical information about a subset of the line flows and bus (node) properties. This information can be used in conjunction with a computational model to infer the topology of the network. We present a Bayesian approach to topological inference that considers a bank of possible topologies. The solution provides a probability for each member in the model bank. The approach has two important features. First, we build a statistical approximation, or emulator, to the computational model, which is too computationally expensive to run a large number of times. Second, we use the emulator in an importance sampling scheme to estimate the probabilities. The resulting algorithm is fast enough to use in real time and very accurate. This article has online supplementary materials. [ABSTRACT FROM AUTHOR]

Although electricity transmission systems are typically very robust, the impacts that arise when they are disrupted motivate methods for analyzing outage risk. For example, N - k interdiction models were developed to characterize disruptions by identifying the sets of k power system components whose failure results in "worst case" outages. While such models have advanced considerably, they generally neglect how failures outside the power system can cause large-scale outages. Specifically, failures in natural gas pipeline networks that provide fuel for gas-fired generators can affect the function of the power grid. In this study, we extend N - k interdiction modeling to gas pipeline networks. We use recently developed convex relaxations for natural gas flow equations to yield tractable formulations for identifying sets of k components whose failure can cause curtailment of natural gas delivery. We then present a novel cutting-plane algorithm to solve these problems. Finally, we use test instances to analyze the performance of the approach in conjunction with simulations of outage effects on electrical power grids. [ABSTRACT FROM AUTHOR]

Highlights • Networked microgrids connected via a medium-voltage distribution system have been previously proposed as a cost-effective solution for improving distribution system resilience during severe weather events. • A method is developed to evaluate the benefits of networked microgrids for improving resilience. • The method is applied to two large real-world distribution systems. • Results confirm that for some combinations of microgrid construction and line hardening costs a combination of line hardening and network microgrids is the most cost-effective solution to meet resilience requirements. Abstract Electrical distribution systems are often vulnerable to severe weather. Upgrades, such as microgrids, system hardening, and line redundancy, can greatly reduce the number of electrical outages during such extreme events. More recently, the networking of microgrids has received attention as a solution to further improve the resilience of distribution feeders. Although these upgrades have the potential to improve resilience, a barrier to their execution is a lack of tools and approaches that support systematic exploration of the underlying parameters of these upgrades and their cost vs. resilience tradeoffs.To address this gap, we develop a method for designing resilient distribution grids, including networked microgrids, by posing the problem as a two-stage stochastic program. When resilience is defined as the ability of a network to supply load immediately following a storm event, we show that a decomposition-based heuristic algorithm scales to a 1200-node distribution system. We also vary the study parameters, i.e., the cost of microgrids relative to system hardening and target resilience metrics. In this study, we find regions in this parametric space that correspond to different resilient distribution system architectures, such as individual microgrids, hardened networks, and a transition region that suggests the benefits of microgrids networked via hardened circuit segments. [ABSTRACT FROM AUTHOR]

The growing dependence of electric power systems on gas-fired generators to balance fluctuating and intermittent production by renewable energy sources has increased the variation and volume of flows withdrawn from natural gas transmission pipelines. Adapting pipeline operations to maintain efficiency and security under these dynamic conditions requires optimization methods that account for substantial intraday transients and can rapidly compute solutions in reaction to generator re-dispatch. Here, we present a computationally efficient method for minimizing gas compression costs under dynamic conditions where deliveries to customers are described by time-dependent mass flows. The optimization method uses a simplified representation of gas flow physics, provides a choice of discretization schemes in time and space, and exploits a two-stage approach to minimize energy costs and ensure smooth and physically meaningful solutions. The resulting large-scale NLPs are solved using an interior point method. The optimization scheme is validated by comparing the solutions with an integration of the dynamic equations using an adaptive timestepping differential equation solver, as well as a different, recently proposed optimal control scheme. The comparison shows that solutions to the discretized problem are feasible for the continuous problem and also practical from an operational standpoint. The results also indicate that our scheme produces 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 6,000 kilometers of total pipeline. The online supplement is available at https://doi.org/10.1287/ijoc.2018.0821. [ABSTRACT FROM AUTHOR]