Home | Project Leaders | NPS Department of Operations Research

The VEGA Project

Under sponsorship of the U.S. Department of Energy and U.S. Department of Homeland Security, researchers in the Operations Research Department at the Naval Postgraduate School and in the Department of Electrical and Computer Engineering at University of Texas are investigating the use of optimization techniques for analyzing the security and resilience of electrical power grids against disruptions caused by terrorist attacks.

References:

Salmerón, J. and Wood, K., 2015, "The Value of Recovery Transformers in Protecting an Electric Transmission Grid Against Attack," IEEE Transactions on Power Systems, Vol. 30, pp. 2396-2403

Salmerón, J., Alderson, D., and Brown, G., 2013, "Analyzing the Resilience of Electric Power Infrastructure Supporting Vandenberg Air Force Base (U)," National Security Operations Research, 1, 2.

Salmerón, J., Wood, R.K. and Baldick, R. (2009), "Worst-Case Interdiction Analysis of Large-Scale Electric Power Grids," IEEE Transactions on Power Systems, Vol. 24, pp. 96-104. ABSTRACT—This paper generalizes Benders decomposition to maximize a nonconcave objective function and uses that decomposition to solve an “electric power grid interdiction problem.” Under one empirically verified assumption, the solution to this bilevel optimization problem identifies a set of components, limited by cardinality or “interdiction resource,” whose destruction maximizes economic losses to customers (and can thereby guide defensive measures). The decomposition subproblem typically incorporates a set of dc optimal power-flow models that cover various states of repair after an attack, along with a load-duration curve. Test problems describe a regional power grid in the United States with approximately 5000 buses, 6000 lines, and 500 generators. Solution time on a 2-GHz personal computer is approximately one hour.

Brown, G., Carlyle, M., Salmerón, J. and Wood, K., 2006, "Defending Critical Infrastructure," Interfaces, Vol. 36, 530-544. This paper featured in INFORMS Editor's Cut "Confronting Public Problems with OR," reprinted April 2016.

Salmerón, J., Wood, K. and Baldick, R., 2004, "Analysis of Electric Grid Security under Terrorist Threat," IEEE Transactions on Power Systems, Vol. 19, 905-912. ABSTRACT—We describe new analytical techniques to help mitigate the disruptions to electric power grids caused by terrorist attacks. New bilevel mathematical models and algorithms identify critical system components by creating maximally disruptive attack plans for terrorists assumed to have limited offensive resources. We report results for standard reliability test networks to show that the techniques identify critical components with modest computational effort.

 - M.S. Theses

LT Douglas Jonart (2008), "Interdicting the United States Power Grid: A Revision Incorporating Exact Solutions," Thesis (M.S. in Systems Technology [Command, Control, and Communication (C3)]), Naval Postgraduate School, Advisor: Javier Salmerón (restricted access).

Rose, Robert (2007), “Defending Electrical Power Grids,” Thesis (M.S. in Operations Research), Naval Postgraduate School. Advisors: Javier Salmerón, R. Kevin Wood. ABSTRACT: This thesis considers the problem of protecting an electrical power grid against a potential attack on its physical infrastructure.  We develop a mathematical model, called “Defense of Known Interdictions” (DKI), that identifies the optimal set of components to defend in an electrical power grid given limited defensive resources.  For a small test network, we show that defending fewer than 10% of the buses reduces the possible disruption from an attack by over 20%.  Previous research has developed optimization models, called I-DCOPF, to find optimal or near optimal interdiction plans for electrical power grids.  DKI solution time is determined by I-DCOPF solution time.  We develop a model, called the Network Dual Relaxation (NDR), to replace I-DCOPF and reduce solution times.  NDR approximates electrical power grid behavior as a minimum cost network flow and uses this approximation to quickly estimate a lower bound for the exact interdiction model.  We test NDR on a portion of the North American power grid with a computational limit of 6000 seconds. Results with ten buses defended show that NDR finds solutions that are, on average, 40% better than those of the exact I-DCOPF model with a significant reduction in computational time.

Ang, Chee Chien (2006), “Optimized Recovery of Interdicted Electrical Grids and Other Networks,” Thesis (M.S. in Operations Research), Naval Postgraduate School. Advisors: Javier Salmerón, R. Kevin Wood. ABSTRACT—This thesis formulates and solves a mixed-integer program to plan the recovery of an electrical power transmission grid that has been damaged by a natural disaster or terrorist attack.  The damage can be extensive and recovery can take weeks or months.  An efficient recovery plan that maximizes the utilization of repair resources can help ensure swift restoration of services.  The network recovery-planning model is implemented in GAMS (General Algebraic Modeling System) and uses CPLEX as the solver.  An electrical grid based on IEEE’s 300-bus transmission network is used for testing.  To simulate varying degrees of damage to the network, we choose up to 20% of the grid’s components to be placed out of service.  Based on the availability of repair resources and penalties for unserved demand, the model produces a repair schedule that minimizes the cost of power shed.  We demonstrate that for a network with up to 8% of its components damaged, the model can produce an optimal recovery plan within 20 minutes on a 2 GHz personal computer.  For our largest test-case with 20% of network components damaged, the recovery plan is within 7% of optimal after 1 hour of solver time.

LCDR David Carnal (2005), "An Enhanced Implementation of Models for Electric Power Grid Interdiction," Thesis (M.S. in Operations Research), Naval Postgraduate School, Advisor: Kevin Wood; Second Reader; Javier Salmerón. ABSTRACT—This thesis evaluates the ability of the Xpress-MP software package to solve complex, iterative mathematicalprogramming problems. The impetus is the need to improve solution times for the VEGA software package, which identifies vulnerabilities to terrorist attacks in electric power grids. VEGA employs an iterative, optimizing heuristic, which may need to solve hundreds of related linear programs. This heuristic has been implemented in GAMS (General Algebraic Modeling System), whose inefficiencies in data handling and model generation mean that a modest, 50-iteration solution of a real-world problem can require over five hours to run. This slowness defeats VEGA's ultimate purpose, evaluating vulnerability-reducing structural improvements to a power grid. We demonstrate that Xpress-MP can reduce run times by 60%-85% because of its more efficient data handling, faster model generation, and the ability, lacking entirely in GAMS, to solve related models without regenerating each from scratch. Xpress-MP's modeling language, Mosel, encompasses a full-featured procedural language, also lacking in GAMS. This language enables a simpler, more modular and more maintainable implementation. We also demonstrate the value of VEGA's optimizing heuristic by comparing it to rule-based heuristics rules adapted from the literature. The optimizing heuristic is much more powerful.

Maj Timothy Schneider (2005), "Interdicting the United States Power Grid,"  Thesis (M.S. in Operations Research), Naval Postgraduate School, Advisor: Javier Salmerón (restricted access).

Alvarez, R. (2004), "Interdicting electrical power grids," Thesis (M.S. in Operations Research), Naval Postgraduate School. Advisors: Javier Salmerón, R. Kevin Wood. ABSTRACT—This thesis explores Benders decomposition for solving interdiction problems on electric power grids, with applications to analyzing the vulnerability of such grids to terrorist attacks. We refine and extend some existing optimization models and algorithms and demonstrate the value of our techniques using standard reliability test networks from IEEE. Our implementation of Benders decomposition optimally solves any problem instance, in theory. However, run times increase as Benders’ cuts are added to the master problem, and this has prompted additional research to increase the decomposition’s efficiency. We demonstrate empirical speed ups by dropping slack cuts, solving a relaxed master problem in some iterations, and using integer but not necessarily optimal master-problem solutions. These mixed strategies drastically reduce computation times. For example, in one test case, we reduce the optimality gap, and the time that it takes to achieve this gap, from 16% in 75 hours to 5% in 16 minutes.

Stathakos, D. (2003), "An enhanced graphical user interface for analyzing the vulnerability of electrical power systems to terrorist attacks," Thesis (M.S. in Operations Research), Naval Postgraduate School. Advisors: Javier Salmerón, R. Kevin Wood. ABSTRACT—This thesis develops a Graphical User Interface (GUI) to represent electric power grids subject to interdiction (attack) by terrorists. The work enhances the prototypic One-line Diagram (OD) representations of electric power networks in the VEGA 1.0 decision-support system (Vulnerability of Electrical Power Grids Analysis, version 1.0). Conforming to Windows standards, the new OD GUI incorporates advanced graphical features, which help the user visualize the model and understand the consequences of interdiction. The new ODs also capture the details of system restoration over time following an attack. The enhanced OD GUI has been incorporated into the updated version of the system, VEGA 2.0.

 - Technical Reports

Salmerón, J., Alderson, D., and Brown, G., 2017, "Resilience Report: Analysis of Hawaiian Electric Power Grid to Physical Attack (U)," Technical Report, Naval Postgraduate School (forthcoming). (Restricted access via DHS)

Alderson, D., Brown, G., Chankij, M., Mislick, G., Nussbaum, D., Salmerón, J., and Schramm, H., 2014, "Assessing and Improving Resiliency of the Air Force Jet Fuel Distribution System on Guam, Including Recommendations and Cost Estimates for Major Hardening Military Construction (U)," Winner 2014 Military Operations Research Society Barchi Prize.

Salmerón, J., Alderson, D., Brown, G., and Wood, K., 2012, "Resilience Report: The Guam Power Authority Electric Power Grid: Analyzing the Vulnerability to Physical Attack (U)," Technical Report, Naval Postgraduate School, NPS-OR-12-002. (Restricted access)

Salmerón, J., Alderson, D. and Brown, G., 2011, "Resilience Report: Electric Power Infrastructure Supporting Mission Assurance at Vandenberg Air Force Base (U)," Technical Report, Naval Postgraduate School, NPS-OR-11-008. (Restricted access)

Salmerón, J. and Wood, K., 2009, "Final Report on DOE Research Project DE-AI02-05ER25670: Reducing the Vulnerability of Electric Power Grids to Terrorist Attacks," Project Report, Naval Postgraduate School, NPS-OR-09-003-PR. (Restricted access)

Salmerón, J., Wood, K. and Baldick, R., 2005, "Optimizing electric grid design under asymmetric threat (III)," Technical Report, Naval Postgraduate School, NPS-OR-05-005. (Restricted access)

Salmerón, J., Wood, R.K. and Baldick, R. (2004), "Optimizing electric grid design under asymmetric threat (II)," Naval Postgraduate School, D 208.14/2:NPS-OR-04-001. ABSTRACT—This research extends our earlier work to improve the security of electric power grids subject to disruptions caused by terrorist attacks. To identify critical system components (e.g., transmission lines, generators, transformers), we devise bilevel optimization models that identify maximally disruptive attack plans for terrorists, who are assumed to have limited offensive resources. A new model captures the dynamics of system operation as a network is repaired after an attack, and we adapt an earlier heuristic for that model’s solution. We also develop a new, mixed-integer programming model (MIP) for the problem; a model that can be solved exactly using standard optimization software, at least in theory. Preliminary testing shows that optimal solutions are readily achieved for certain standard test problems, although not for the largest ones, which the heuristic seems to handle well. However, optimal solutions do provide a benchmark to measure the accuracy of the heuristic: The heuristic typically achieves optimality gaps of less than 10%, but occasionally the gap reaches 25%. Research will continue to refine the heuristic algorithm, the MIP formulation, and the algorithms to solve it. We also demonstrate progress made towards a graphical user interface that allows performing our interdiction analysis in a friendly environment.

Salmerón, J., Wood, K. and Baldick, R., 2003, "Optimizing electric grid design under asymmetric threat," Technical Report, Naval Postgraduate School, NPS-OR-03-002.

 - Technical Meeting Participation

Salmerón, J. and Wood, K. "The Value of a Spare Transformer Inventory to an Electric Power Grid's Security against Attack," INFORMS, San Francisco, CA, 9-12 Nov. 2014

Salmerón, J. and Wood, K. "Electric Power Grid Interdiction: The Value of Spare Transformers," IFORS, Barcelona, Spain, 13-18 July 2014.

Salmerón, J., Alderson, D., Brown, G. and Wood, K. "The Guam Power Authority Electric Power Grid: Analyzing Vulnerability to Physical Attack," Military Operations Research Society Symposium, Washington, D.C., 17-20 June 2013.

Salmerón, J. and Wood, K. "Worst-Case Interdiction, and Defense, of Electric Power Grids," 79th Military Operations Research Society Symposium, Monterey, California, 20-23 June 2011.

Alderson, D., Brown, G., Carlyle, W., Salmerón, J., and Wood, K., "Red and Blue Teams: Defending Critical Infrastructure from Intelligent Adversaries and Worst-Case Disruptions," invited tutorial, Military Operations Research Society Special Meeting: Optimizing Investment in Critical Infrastructure Protection, Alexandria, Virginia, November 15, 2010.

Wood, K. and Salmerón, J., "U.S. power grids: Evaluating and mitigating vulnerability to terrorist attack," INFORMS Annual Meeting, San Diego, California, 11-14 October 2009.

Salmerón, J., Baldick, R. and Wood, K., "Worst-Case Interdiction, and Defense, of Large-Scale Electric Power Grids," 20th International Symposium on Mathematical Programming, Chicago, Illinois, 23-28 August 2009.

Brown, G., Carlyle, W.M., Salmerón, J. and Wood, K., "Interdiction at NPS: From Deterministic to Game-Theoretic Models," XIV Latin Ibero-American Congress on Operations Research, Cartagena de Indias, Colombia, 9-12 September 2008.

Brown, G., Carlyle, W.M., Salmerón, J. and Wood, K., "Stackelberg Games for Adversarial Risk Analysis and Risk Management," Workshop on Decision Modeling and Behavior in Uncertain and Complex Environments, Tucson, Arizona, 29 February – 1 March 2008.

Salmerón, J. and Wood, K., "Trilevel Models for Protecting Electric Power Grids," INFORMS Annual Meeting, Seattle, Washington, 4-7 November 2007.

Salmerón, J., Wood, K. and Baldick, R., "VEGA: Vulnerability of Electric Grids Analyzer," STRATCOM, Global Innovation and Strategy Center, Omaha, Nebraska, 12 June 2006.

Brown, G., Carlyle, W.M., Salmerón, J. and Wood, K., "Trilevel Models for Protecting Critical Infrastructure," INFORMS Annual Meeting, Pittsburgh, Pennsylvania, 5-8 November 2006.

Brown, G., Carlyle, M., Salmerón, J. and Wood, K., "Attack and Defense of Critical Infrastructure," REDTEAM2006, Sandia National Laboratories, Albuquerque, New Mexico, 2-4 May 2006.

Salmerón, J., Wood, K. and Baldick, R., "VEGA: Vulnerability of Electric Grids Analyzer," REDTEAM2006, Sandia National Laboratories, Albuquerque, New Mexico, 2-4 May, 2006.

Brown, G., Carlyle, W.M., Salmerón, J. and Wood, K., "Bilevel And Trilevel Models For Defending Critical Infrastructure: Risk Analysis Without The Risk," Risk Symposium, Santa Fe, New Mexico, 20-22 March, 2006.

Brown, G., Carlyle, W.M., Salmerón, J. and Wood, K., "Analyzing the Vulnerability of Critical Infrastructure to Attack, and Planning Defenses," invited tutorial, INFORMS Annual Meeting, San Francisco, California, 13-16 November 2005.

Wood, K., Salmerón, J., and Baldick, R., "Identifying Vulnerabilities in Electric Power Networks," CISAC Science and Technology Seminar, Stanford University, Stanford, California, 3 May 2005.

Wood, K., Salmerón, J. and Baldick, R., "Identifying Vulnerabilities in Electric Power Networks," Technology and Security Seminar, Freeman Spogli Institute for International Studies, Stanford University, California, 26 April 2005.

Salmerón, J., Wood, K. and Baldick, R. "Analysis of Electric Grid Security under Terrorist Threat," INFORMS, Denver, Colorado, 24-27 October 2004.

Brown, G., Carlyle, M., Salmerón, J. and Wood, K., "How to build a robust supply chain, or harden the one you have," INFORMS Conference on OR Practice, Cambridge, Massachusetts, 25-27 April 2004.

Brown, G., Carlyle, M., Salmerón, J. and Wood, K., "How to build a robust supply chain, or harden the one you have," INFORMS, Atlanta, Georgia, 19-22 October 2003.