Interdicting electrical power grids
Loading...
Authors
Alvarez, Rogelio E.
Subjects
Advisors
Salmeron, Javier
Date of Issue
2004-03
Date
Publisher
Monterey, CA; Naval Postgraduate School
Language
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.
Type
Thesis
Description
Series/Report No
Department
Organization
Naval Postgraduate School (U.S.)
Identifiers
NPS Report Number
Sponsors
Funder
FUNDED BY: 2002-GT-R-057
Format
xxii, 97 p. : ill. (some col.) ;
Citation
Distribution Statement
Approved for public release; distribution is unlimited.
Rights
This publication is a work of the U.S. Government as defined in Title 17, United States Code, Section 101. Copyright protection is not available for this work in the United States.