  Cascading failures typically occur following a large disturbance in power
systems, such as tripping of a generating unit or a transmission line. Such
failures can propagate and destabilize the entire power system, potentially
leading to widespread outages. One approach to mitigate impending cascading
failures is through controlled islanding, in which a set of transmission lines
is deliberately tripped to partition the unstable system into several disjoint,
internally stable islands. Selecting such a set of transmission lines is
inherently a combinatorial optimization problem. Current approaches address
this problem in two steps: first classify coherent generators into groups and
then separate generator groups into different islands with minimal
load-generation imbalance. These methods, however, are based on computationally
expensive heuristics that do not provide optimality guarantees. In this paper,
we propose a novel approach to controlled islanding based on weak
submodularity. Our formulation jointly captures the minimal generator
non-coherency and minimal load-generation imbalance in one objective function.
We relax the problem to a formulation with bounded submodularity ratio and a
matroid constraint, and propose an approximation algorithm which achieves a
provable optimality bound on non-coherency and load-generation imbalance. The
proposed framework is tested on IEEE 39-bus and 118-bus power systems.
