On the solution of the bilevel programming formulation of the terrorist threat problem

This paper generalizes the "terrorist threat problem" first defined by Salmeron, Wood, and Baldick by formulating it as a bilevel programming problem. Specifically, the bilevel model allows one to define different objective functions for the terrorist and the system operator as well as permitting the imposition of constraints on the outer optimization that are functions of both the inner and outer variables. This degree of flexibility is not possible through existing max-min models. The bilevel formulation is investigated through a problem in which the goal of the destructive agent is to minimize the number of power system components that must be destroyed in order to cause a loss of load greater than or equal to a specified level. This goal is tempered by the logical assumption that, following a deliberate outage, the system operator will implement all feasible corrective actions to minimize the level of system load shed. The resulting nonlinear mixed-integer bilevel programming formulation is transformed into an equivalent single-level mixed-integer linear program by replacing the inner optimization by its Karush-Kuhn-Tucker optimality conditions and converting a number of nonlinearities to linear equivalents using some well-known integer algebra results. The equivalent formulation has been tested on two case studies, including the 24-bus IEEE Reliability Test System, through the use of commercially available software.