homebannerbanner

Home | Project Leaders | NPS Department of Operations Research

The VEGA Project

View a PowerPoint PresentationUnder sponsorship of the U.S. Department of Energy, 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:

 - Publications

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.

Salmerón, J., Wood, R.K. and Baldick, R. (2004), "Analysis of electric grid security under terrorist threat," INFORMS Annual Meeting, Denver, CO. 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

Rose, Robert (2007) “Defending Electrical Power Grids,” Thesis (M.S. in Operations Research), Naval Postgraduate School. Advisors: Javier Salmeron, 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 Salmeron, 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.

Alvarez, R. (2004), "Interdicting electrical power grids," Thesis (M.S. in Operations Research), Naval Postgraduate School. Advisors: Javier Salmeron, 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., 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.

 

 - Technical Meeting Participation

Salmeron, J. and Wood, K. INFORMS Annual Meeting, Seattle, Washington, U.S.A., 4-7 November 2007, “Trilevel Models for Protecting Electric Power Grids.”

Salmeron, J., Wood, K. and Baldick, R., STRATCOM, Global Innovation and Strategy Center, Omaha, NB, U.S.A., 12 June, 2006, “VEGA: Vulnerability of Electric Grids Analyzer.”

Salmeron, J., Wood, K. and Baldick, R., REDTEAM2006, Sandia National Laboratories, Albuquerque, NM, U.S.A., 2-4 May, 2006, “VEGA: Vulnerability of Electric Grids Analyzer.”

Wood, K., Salmeron, J. and Baldick, R., Technology and Security Seminar, Freeman Spogli Institute for International Studies, Stanford University, California, U.S.A., 3 May 2005. “Identifying Vulnerabilities in Electric Power Networks.”

Salmeron, J., Wood, K. and Baldick, R. INFORMS, Denver, Colorado, U.S.A., 24-27 October 2004. “Analysis of Electric Grid Security under Terrorist Threat.”

 - Other Work Describing VEGA

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

Brown, G., Carlyle, W.M., Salmeron, J. and Wood, K., Workshop on Decision Modeling and Behavior in Uncertain and Complex Environments, Tucson, Arizona, U.S.A., February 2008, “Stackelberg Games for Adversarial Risk Analysis and Risk Management.”

Brown, G., Carlyle, W.M., Salmeron, J. and Wood, K. INFORMS Annual Meeting, Pittsburgh, Pennsylvania, U.S.A., 5-8 November 2006, “Trilevel Models for Protecting Critical Infrastructure.”

Brown, G., Carlyle, W.M., Salmeron, J. and Wood, K., REDTEAM2006, Sandia National Laboratories, Albuquerque, NM, U.S.A., 2-4 May, 2006, “Attack and Defense of Critical Infrastructure.”

Brown, G., Carlyle, W.M., Salmeron, J. and Wood, K., Risk Symposium, Santa Fe, NM, U.S.A., 20-22 March, 2006, “Bilevel And Trilevel Models For Defending Critical Infrastructure: Risk Analysis Without The Risk.”

Brown, G., Carlyle, W.M., Salmeron, J. and Wood, K., 2005, “Analyzing the Vulnerability of Critical Infrastructure to Attack, and Planning Defenses,” in Tutorials in Operations Research: Emerging Theory, Methods, and Applications, H. Greenberg and J. Smith, eds., Institute for Operations Research and Management Science, Hanover, MD.

Brown, G., Carlyle, W.M., Salmeron, J. and Wood, K., INFORMS Annual Meeting, San Francisco, California, U.S.A., 13-16 November 2005. “Analyzing the Vulnerability of Critical Infrastructure to Attack, and Planning Defenses,” invited tutorial.

Home | Project Leaders | Webmaster
Privacy | Legal Notices | DoD/Navy Links

This is an official U.S. Navy website. Last updated October 17, 2005.