## 2 Related Work  
The PSIP is essentially a type of graph partitioning problem (GPP) (e.g., see [14; 15; 16]). Theoretically, a power system made up of \(n\) transmission lines has \(2^{n}\) possible choices for system splitting, since each line has two statuses, namely switching on and switching off. The solution approaches in the literature for the minimal generation-load imbalance generally combine graph representation of the power system with heuristics. In [7], a two-stage ordered binary decision diagram (OBDD) method [17] was presented to find islands with minimal generation-load imbalance. However, this method can only deal with the small-scale power network that usually contains less than 40 nodes. As done by [8; 18], the large-scale power system needs to be simplified before being split using this method. Based on slow coherency, [PERSON] _et al._[10] and [PERSON] _et al._[19] presented an islanding algorithm by first constructing a small subnetwork using the center bus. Then, a brute-force search is applied to the subnetwork to determine the edge set whose removal results in the islands with the minimum generation-load imbalance. A graph-based method was introduced, which first simplifies a large-scale power system into a smaller network and then applies a multi-level recursive bisection method to partition the reduced network into the sub-networks with the minimum generation-load imbalance [20]. They proved the effectiveness of their approach by simulation results on the 14 August 2003 blackout in North America. Recently, [PERSON] _et al._[21] proposed a new method for controlled islanding that respects the voltage and reactive power constraints. In this paper, the authors approximated the AC power flow using a piecewise linear line and then split the network into islands using a mixed integer linear programming model. Since 2009, more advanced heuristics were developed to solve power systems of a large scale. As pointed out by [6], most of the existing islanding algorithms are applied to a simplified version or a selected subset of the original power system. Since simplification may omit the optimal solutions, it is preferable to handle the original network directly. Therefore, they proposed a new islanding algorithm based on slow coherency [22] and angle-modulated particle swarm optimization (AMPSO) [23] for the large-scale power systems with up to 118 nodes. The work in [24] formulated the power network partitioning problem as the min-cut problems, where they used a new definition for the capacity of a cut, different from the traditional one. They solved their problems by simple heuristics that are built on the modified version of the approximation algorithm for the node-weighted Steiner tree problem [25]. The work in [26] designed the first neighborhood-based local search algorithm to generate the splitting solutions and tested this algorithm on the IEEE 118-bus system and a real 212-bus system in China. [PERSON] _et al._[27] proposed a constrained spectral clustering-based controlled islanding algorithm that can find islanding solution in polynomial time and has no need to simplify the original network. This algorithm converts the islanding problem into a graph-cut problem and tries to minimize the power-flow disruption. The above-mentioned approaches have two obvious deficiencies. First, they are only capable of handling either the small-scale power system or the reduced version of the large-scale power system. Second, most of these approaches consumed too much time to solve the problem. For instance, the algorithm by [7] spent around 2.5 s in solving the problem with only 30 nodes, which is unacceptable in real practice. Therefore, it is necessary to develop an approach that can identify the high-quality solutions for the large-scale power system within a short computation time.