Accession Number:

ADA422163

Title:

Interdicting Electrical Power Grids

Descriptive Note:

Master's thesis

Corporate Author:

NAVAL POSTGRADUATE SCHOOL MONTEREY CA

Personal Author(s):

Report Date:

2004-03-01

Pagination or Media Count:

121.0

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 decompositions 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.

Subject Categories:

  • Electrical and Electronic Equipment
  • Computer Systems
  • Defense Systems
  • Command, Control and Communications Systems

Distribution Statement:

APPROVED FOR PUBLIC RELEASE