About the Competition
Since the dawn of the age of electrification, electric power system engineers and operators have been required to manage the real-time matching of instantaneous electricity generation and demand – especially in the absence of cost effective and ubiquitous electricity storage. Achieving a continuous match between supply and demand requires utilities, grid operators, and other stakeholders to use a variety of sophisticated energy management systems (EMS), market management systems (MMS), dynamic security assessment (DSA) tools, and other decision support tools. These systems employ optimization models and algorithms, control systems, and/or simulations that cover a wide spectrum of applications that vary in mathematical program type, structure, complexity, and timescale. Decision stages include long-term analysis (e.g., investment planning), midterm analysis (maintenance scheduling, outage coordination, and various reliability and stability assessments), operational planning stages (e.g., day-ahead security constrained unit commitment), and real-time operations and situational awareness.
A number of emerging trends will substantially alter the planning, operations, control, and reliability standards of electric grids over the next several decades. These trends include the high penetration of stochastic resources for which forecasts are uncertain (such as wind and solar), changing electricity demand patterns, and the improving cost effectiveness of distributed energy resources (including storage). Operational protocols and software support systems have long since treated bulk power plants as the primary source of operational flexibility necessary to ensure a reliable and efficient operation. Instead, there is a paradigm shift where flexible bulk resources are being replaced by bulk stochastic resources (wind and solar) with limited flexibility while distributed energy resources are emerging to provide flexibility. Innovative grid software is necessary to plan under and adapt to growing penetrations of stochastic resources for which availability is both more variable than conventional generators and highly probabilistic, at best. The expected growth in system complexity will require the development of substantially improved grid software to assist grid operators to ensure not just a continuous supply of reliable electricity but to achieve a sustainable, clean, and affordable electric power economy, a necessity for any advanced society.
Many new optimization methods have been proposed in the research community in recent years and many claims have been made regarding the possible practical benefits that these new algorithms might offer utilities and power grid operations in general. However, today, it is extremely difficult to compare relative strengths and weaknesses of different proposed approaches. The vast majority of reports only test new algorithms on either relatively small-scale power network models, which often must be heavily modified to satisfy the modeling requirements specific to individual algorithms, or on proprietary datasets that inherently cannot be released for wide-spread performance testing. Computational experiments are also typically conducted on a variety of systems, ranging from commodity laptops to large-scale clusters with many thousands of nodes. Even small changes in how specific constraints are modeled or which constraints are considered can have significant implications for algorithm selection and performance as well as solution quality. Electrification was chosen as the greatest achievement of the 20th century by the National Academy of Engineering based on technical achievements for one of the most complex engineered systems that then forms a backbone for any modern society. A new paradigm for the testing and evaluation of emerging software solutions is needed to accelerate the adoption of transformational technologies for this critical and complex engineered system.
In response, ARPA-E has announced the GO Competition. The goal of the GO Competition is to accelerate the development of transformational and disruptive methods for solving the most pressing power system problems. The GO Competition will be staged as a series of challenges in power systems to address emerging needs and new technologies on the grid. Challenge 1 focused on security-constrained optimal power flow (SCOPF). With this competition, ARPA-E aims to provide fair and transparent comparisons of industrially-relevant algorithm performance on high-fidelity, open-access, large-scale power system models and a platform for the identification of transformational and disruptive methods for solving power system optimization problems.
The optimal power flow (OPF) problem is the central optimization challenge underlying a large suite of grid planning and operational tools. Simply stated, the OPF problem is that of finding the optimal dispatch and control settings for power generation, flexible customer demand, energy storage, and grid control equipment that maximize one or more grid objectives, while the SCOPF problem additionally considers security constraints.[1],[2],[3] In order to be deployable, the recommended settings must satisfy all physical constraints of electric power infrastructure and applicable operating standards. These standards include, but are not limited to, minimum and maximum voltages at each node (bus), minimum and maximum power generation from each generator, thermal transmission constraints, proxy stability constraints, and constraints to ensure the reliability of the system while responding to unexpected events and outages (i.e., contingencies). For a more complete history and formal problem formulation, we refer the reader to a paper authored by the Federal Energy Regulatory Commission (FERC).[4]
The core SCOPF solution methods predominantly used in industry today were designed in an era when computers were far less capable and more costly than they are currently and formal general purpose optimization solvers were in their infancy. Grid operators, power system software vendors, and the research community were required to make a range of simplifying assumptions, most commonly a set of linearizing assumptions that ignore voltage and reactive power, referred to as a direct current optimal power flow (DCOPF). While many proprietary variations on SCOPF models, approximations, and solution techniques have been developed over the past decades by industry vendors, the most commonly used optimization software packages, including production cost models, security-constrained unit commitment (SCUC), and security-constrained economic dispatch (SCED) tools rely on linear OPF assumptions such as the assumptions found in a classical DCOPF problem. Despite improvements in formulations, approximation techniques, and solvers, there are no tools currently in widespread use in industry that use the full AC power flow equations (without linearizing assumptions) and simultaneously co-optimize both real and reactive power generation.
The SCOPF tools in use today often result in conservative solutions that must be iteratively checked for physical feasibility before implementation. The development and demonstration at scale of SCOPF solution methods providing physically feasible solutions and capable of optimizing both real and reactive power generation and demand within the time limits required for practical application remains an open, unsolved problem. Achieving these capabilities is expected to become critical in the future as electric power systems evolve to include more widely distributed and stochastic resources, especially as SCOPF becomes more important in the context of electric distribution systems.
There are reasons to believe that recent advances could enable significantly improved SCOPF approaches. Dramatic improvements in computational power and advancements in optimization solvers in recent years have prompted research on new approaches to grid operations and new approaches to solve SCOPF and other grid problems.[5]
Since the turn of the millennium, the performance of the most powerful supercomputers has increased by almost four orders of magnitude while the cost per computational step has dropped by approximately the same factor.[6],[7] Improvements in optimization and search methods have evolved similarly, especially those related to mixed integer programming (MIP) and heuristic-based optimization methods. The relative speed of commercial general-purpose solvers, such as CPLEX and GUROBI, has also increased by over three orders of magnitude on fixed hardware.[8],[9] Cloud computing, which can be used to leverage many of these gains, has also started to gain more widespread interest within the power system engineering community.[10]
In tandem, many new approaches to solve SCOPF problems have been proposed in the literature in recent years; it appears increasingly likely that scalable and more accurate approaches to solve the SCOPF problem may be within reach. For example, recent research has moved from linear approximations to convex relaxations for the classical SCOPF problem. Fast and accurate convex relaxations have been formulated where the global optimum can be found efficiently using quadratic convex, semi-definite, and second order cone programming approaches.[11],[12],[13],[14],[15] Furthermore, it has been shown that there are situations when a convex relaxation of the OPF problem can still find the global optimum to the original non-convex mathematical program.[16],[17] Distributed and parallelizable SCOPF algorithms have also been proposed, for example, using the alternating direction method of multipliers (ADMM), suggesting that SCOPF solution algorithms can be designed that leverage more advanced computational hardware.[18],[19],[20]These same algorithms could enable the real-time coordination and optimization of large numbers of distributed energy resources. Advances in general optimization methods, as well as those from other fields, may lend insights to solve SCOPF problems. For example, work in machine learning has focused on efficiently finding solutions to non-convex optimization problems. Methodologies developed, such as new variations on stochastic gradient descent, may help efficiently find solutions to the non-convex ACOPF problem.[21],[22],[23] SCOPF problems that solve both pre-contingency and post-contingency states may also benefit from recent research into decomposition methods or stochastic optimization algorithms that seek to exploit a similar two-stage problem structure.[24],[25] Finally, many unique methodologies using techniques such as genetic algorithms, neural networks, fuzzy algorithms, and holomorphic embedding have also emerged claiming, in many cases, to revolutionize solution methods for SCOPF. [26],[27]
The end-result has been numerous research projects and papers on improved grid optimization strategies and many new algorithms that may be able to significantly impact grid operation and control. However, most of these efforts have not yet moved past the early research stage; a goal of the ARPA-E GO Competition is to help advance this research and bring to industry new and transformative grid software.
Despite numerous recent research projects and papers on improved grid optimization strategies, most new advances have struggled to mature past the early research stage. Few mechanisms currently exist to allow for the direct comparison of solution methods. Therefore, it is difficult to know the precise relative strengths and weaknesses of different algorithms.
Comparisons of new algorithms can be facilitated by the creation of formal prize competitions. Many other industries have successfully employed prize competitions to efficiently advance research efforts; for example, teams competing for the $10 million Ansari X PRIZE collectively spent over $100 million to develop reusable manned spacecraft.[28] Research at Harvard Business School has provided strong evidence that prize competitions can lead to faster, more efficient, and more-creative problem solving.[29] When employed properly, innovation prizes can result in better problems and solutions, more efficient use of funding, and engagement across broad communities of stakeholders. Established industries have been transformed by competitions around well posed problems that engage multi-disciplinary teams and those without traditional subject matter expertise. ARPA-E strongly believes that the next generation of grid optimization algorithms can benefit greatly from the advantages of innovation prizes.
It is important to note that a necessary first step for any meaningful SCOPF competition must be the development of many small, medium, and large-scale, realistic power system network descriptions and operating scenarios defining a variety of challenging operating conditions (reflecting both the existing electric power system and that in the future). The primary objective of the ARPA-E GRID DATA (Generating Realistic Information for the Development of Distribution And Transmission Algorithms) program[30], launched in early 2016, is the development of these datasets, an example of which is depicted in Figure 1. The GRID DATA program will provide many of the power system datasets to be used in the upcoming GO Competition.
Figure 1. 10,000 Node Synthetic Network Model on the Footprint of the Western United States.[31]
For Challenge 1 of the competition, datasets containing power system network models with corresponding scenarios and contingencies will be released at the start of the GO Competition Challenge 1, which will allow Entrants to test their SCOPF algorithms prior to submitting the algorithms for Trial Event 1, Trial Event 2, and the Final Event (official scoring for the determination of prizes). The problem formulation and modeling approach described at https://gocompetition.energy.gov/challenges/challenge-1 will be used for solution evaluation. Entrants will be permitted and encouraged to use any approximation or reformulation of the official problem formulations, alternative modeling conventions, and/or solution methods within their own software; however, the resulting solution must comply with the official formulation. Indeed, we anticipate Entrants will use a variety of model formulations (to enhance computational efficiency and/or promote finding a solution) and will use a mix of formal optimization solution methods and unique heuristics. Entrants are welcome to interpret the fundamental nature of the SCOPF problem and its application as they see fit; for example, Entrants may choose to mathematically decompose the problem in various ways. Regardless of the method and model formulation used within each Entrant’s software, all Entrants will be required to provide their solution (variable setpoints) in a form that is compatible with the selected, published competition problem formulation. It is important to note that the formulation employs an Alternating Current (AC) formulation, though Entrants do not have to employ full AC optimization methods within their competition software.
Entrants will interact with the competition via a hosted computational platform with a web front-end portal (https://gocompetition.energy.gov/). Algorithms will be submitted for formal evaluation (and scoring) by the official competition platform throughout all challenges of the competition. Submissions can either be source code that must be compiled, linked, and executed, interpreted and executed, or a binary execution file. Each submission will be run on the controlled, secure evaluation platform with no external communications. The competition evaluation platform will provide access to several popular licensed solvers (please refer to the competition website for an up-to-date list of supported solvers). Solutions requiring licensed software not provided by the platform will have to be self-contained.
Public leaderboards will be maintained during the competition on the web portal as described below. Entrants can participate as individuals or in teams. Please see the Rules Document posted on the GO Competition website (https://gocompetition.energy.gov/competition-rules) for more information.
The overall goal of the GO Competition is running a competition that is fair, transparent and results in the accelerated development of disruptive new grid optimization algorithms that can robustly address existing and emerging power system challenges. Participants should proffer an opinion on any structure which results in this ultimate goal. The goal of Challenge 1 to identify grid optimization strategies and algorithms that are beyond the state-of-the-art currently available. Challenge 1 is seeking pioneering solutions to the problem and participants are encouraged to comprehensively redesign conventional approaches.
Improved SCOPF algorithms can yield significant benefits. Recent studies have suggested that enhanced SCOPF algorithms can offer as much as 5-10% reductions in total U.S. electricity cost by improving our management of grid resources in order to reduce network and operational limitations, corresponding to a savings of $6-$19B.[32],[33] In addition to monetary savings, improved optimization algorithms are likely to help ensure reliable system operation as power flows become more dynamic.[34]To fully realize the potential benefits of renewable generation as well as recently developed electric transmission power flow controllers, distribution automation technologies, distributed energy resources, and energy storage, software support tools will require more complex (and fundamentally nonlinear) grid operation optimization and dispatch algorithms. Furthermore, as the number of controllable resources connected to both transmission and distribution systems grow substantially, along with the reliance on stochastic resources, it is important to examine approaches that will handle the increasing complexities driven by the size, non-convexities, and uncertainties associated with power grid management problems. Advances in optimization methods and decision support tools are paramount to overcome these complicating factors and to reduce the reliance on operator intuition and the reliance on conventional technologies. In this context, the importance of new SCOPF methods was recently recognized by the National Academies.[35]
The level of effort needed to advance the field is significant. This is a hard problem that has been long studied. Prizes will be awarded to top performers in each Challenge; these may include a cash award or follow-on research funding for an ARPA-E managed project.
References
[1] J. Carpentier, “Contribution to the economic dispatch problem,” Bulletin de la Société Française des Électriciens, ser. 8, vol. 3, pp. 431‐447, 1962.
[2] H. W. Dommel and W. F. Tinney, “Optimal power flow solutions,” IEEE Transactions on Power Apparatus and Systems, vol. 87, no. 10, pp 1866-1876, October 1968.
[3] There are a variety of specific applications for OPF. The specific objective function and the constraints can vary widely. In many applications, where demand is considered fixed, the objective is considered to be minimization of total generation cost.
[4] M. B. Cain, R. P. O’Neill, and A. Castillo, “History of optimal power flow and formulations,” Federal Energy Regulatory Commission, Washington, DC, August 2013, http://www.ferc.gov/industries/electric/indus-act/market-planning/opf-papers/acopf-1-history-formulation-testing.pdf.
[5] P. Panciatici et al., “Advanced optimization methods for power systems,” Proceedings of the 18th Power System Computation Conference, Wroclaw, Poland, August 2014, pp. 1-18, doi: 10.1109/PSCC.2014.7038504.
[6] TOP 500, The List, http://www.top500.org/.
[7] Machine Intelligence Research Institute, "Exponential and non-exponential trends in information technology", https://intelligence.org/2014/05/12/exponential-and-non-exponential/.
[8] GUROBI Optimization, http://www.gurobi.com.
[9] T. Koch et al., “MIPLIB 2010,” Mathematical Programming Computation, vol. 3, no. 2, pp. 103-163, June 2011, doi: 10.1007/s12532-011-0025-9
[10] J. Goldis et al., “Use of cloud computing in power market simulations,” Presentation at FERC Staff Technical Conference on Increasing Real-Time and Day-Ahead Market Efficiency through Improved Software, Washington, DC, June 2014.
[11] S. Low, "Convex relaxation of optimal power flow, Part I: Formulations and equivalence," IEEE Transactions on Control of Network Systems, vol. 1, no. 1, pp. 15-27, March 2014, doi: 10.1109/TCNS.2014.2309732.
[12] S. Low, “Convex relaxation of optimal power flow, Part II: Exactness,” IEEE Transactions on Control of Network Systems, vol. 1, no. 2, pp. 177-189, May 2014, doi: 10.1109/TCNS.2014.2323634.
[13] R. Madani, S. Sojoudi, and J. Lavaei, "Convex relaxation for optimal power flow problem: Mesh networks," IEEE Transactions on Power Systems, vol. 30, no. 1, pp. 199-211, May 2014, doi: 10.1109/TPWRS.2014.2322051.
[14] D. Molzahn et al., "Implementation of a large-scale optimal power flow solver based on semidefinite programming," IEEE Transactions on Power Systems, vol. 28, no. 4, pp. 3987-3998, April 2013, doi: 10.1109/TPWRS.2013.2258044.
[15] C. Coffrin, H. Hijazi, and P. Van Hentenryck, “Strengthening the SDP relaxation of AC power flows with convex envelopes, bound tightening, and valid inequalities,” IEEE Transactions on Power Systems, vol. 32, no. 5, pp. 3549-3558, September 2017, doi: 10,1109/TPWRS.2016.2634586.
[16]J. Lavaei and S. Low, "Zero duality gap in optimal power flow problem," IEEE Transactions on Power Systems, vol. 27, no. 1, pp. 92-107, August 2011, doi: 10.1109/TPWRS.2011.2160974.
[17] L. Gan et al., "Exact convex relaxation of optimal power flow in radial networks," IEEE Transactions on Automatic Control, vol. 60, no. 1, pp. 72-87, June 2014, doi: 10.1109/TAC.2014.2332712.
[18] A. Sun, D.T. Phan, and S. Ghosh, “Fully decentralized AC optimal power flow algorithms,” IEEE Power and Energy Society General Meeting, Vancouver, BC, Canada, July 2013, doi: 10.1109/PESMG.2013.6672864.
[19] S. Magnússon, P. Weeraddana, and C. Fischione, "A distributed approach for the optimal power flow problem based on ADMM and sequential convex approximations," arXiv preprint arXiv: 1401.4621, January 2014.
[20] B. H. Kim and R. Baldick, "A comparison of distributed optimal power flow algorithms." IEEE Transactions on Power Systems, vol. 15, no. 2, pp. 599-604, May 2000, doi: 10.1109/59.867147.
[21] P. Jain and P. Kar, “Non-convex optimization for machine learning,” Foundations and Trends in Machine Learning, vol. 10, no. 3-4, pp. 142-336, December 2017, doi: 10.1561/2200000058.
[22] R. Ge et al., “Escaping from saddle points – online stochastic gradient for tensor decomposition,” JMLR: Workshop and Conference Proceedings, vol. 40, pp. 1-46, 2015.
[23] Z. Allen-Zhu and E. Hazan, “Variance reduction for faster non-convex optimization,” Proceedings of the 33rd International Conference on Machine Learning, vol. 48, pp. 699-707, June 2016.
[24] F. Capitanescu et al., “State-of-the-art, challenges, and future trends in security constrained optimal power flow,” Electric Power Systems Research, vol. 81, pp. 1731-1741, 2011.
[25] F. Capitanescu, “Critical review of recent advances and further developments needed in AC optimal power flow,” Electric Power Systems Research, vol. 136, pp. 57-68, 2016.
[26] X. F. Wang, Y. Song, and M. Irving, Modern power systems analysis, New York, NY: Springer Science & Business Media, 2008.
[27] A. Trias, "The holomorphic embedding load flow method," IEEE Power and Energy Society General Meeting, San Diego, CA, July 2012, doi: 10.1109/PESGM.2012.6344759.
[28] Bays, Jonathan. "Using Prizes to Spur Innovation" McKinsey & Company, https://www.mckinsey.com/~/media/McKinsey/Featured%20Insights/Innovation/Using%20prizes%20to%20spur%20innovation/Using%20prizes%20to%20spur%20innovation.pdf.
[29] Pisano, Gary. "You Need an Innovation Strategy" Harvard Business Review, https://hbr.org/2015/06/you-need-an-innovation-strategy.
[30] ARPA-E “Generating Realistic Information for Development of Distribution and Transmission Algorithms (GRID DATA),” Funding Opportunity Announcement Number DE-FOA-0001357, June 2015, https://arpa-e.energy.gov/?q=pdfs/grid-data-de-foa-0001357.
[31] A. B. Birchfield, T. Xu, K. M. Gegner, K. S. Shetye, and T. J. Overbye, “Grid structural characteristics as validation criteria for synthetic networks,” IEEE Transactions on Power Systems, vol. 32, no. 4, pp. 3258-3265, July 2017.
[32] M. Ilic, “Modeling of hardware and systems related transmission limits: the use of AC OPF for relaxing transmission limits to enhance reliability and efficiency,” Presentation at FERC Staff Technical Conference on Increasing Real-Time and Day-Ahead Market Efficiency through Improved Software, Washington, DC, June 2013, http://www.ferc.gov/CalendarFiles/20140411131533-T2-B%20-%20Ilic.pdf.
[33] M. B. Cain, R. P. O’Neill, and A. Castillo, "History of optimal power flow and formulations," Federal Energy Regulatory Commission, Washington, DC, August 2013, http://www.ferc.gov/industries/electric/indus-act/market-planning/opf-papers/acopf-1-history-formulation-testing.pdf.
[34] GE Energy, "Western wind and solar integration study," National Renewable Energy Laboratory, Technical Report No. NREL/SR-550-47434, May 2010, http://www.nrel.gov/docs/fy10osti/47434.pdf.
[35] National Academies of Sciences, Engineering, and Medicine. Analytic Research Foundations for the Next-Generation Electric Grid. Washington, DC: The National Academies Press, 2016. doi: 10.17226/21919.