## 4 Tabu Search
### Initial Solution  
We generate the initial solution using a two-stage approach. In the first stage, we construct a critical subgraph for each coherent generator set. In the second stage, we gradually connect the remaining load nodes to the critical subgraphs, such that the total power imbalance is minimized.  
The critical subgraph is constructed as follows. For each coherent generator set, we arbitrarily select one generator as the root node and then construct a tree from the graph using a breadth-first search process, where every node on a level is visited before going to a lower level. The tree construction process has two characteristics: (1) the tree cannot include the generator node in other coherent generator sets; (2) the process stops as soon as the tree includes all generators in this coherent generator set.  
Figure 4 shows the constructed tree associated with the coherent generator Set 1 with generator Node 1 being the root node, where the critical Subgraph 1 is highlighted by bold lines. Obviously, the nodes in the first level is generator Node 2 and load Node 3, since they are adjacent to generator Node 1. Then, the Level 2 nodes originated from generator Node 2 are generator Node 5 and load Nodes 4 and 6. Since load Node 4 already exists in the tree, it cannot be the child node of load Node 3. Since generator Node 8 belongs to the second coherent generator set, it cannot be the child of load Node 6. Following the above extension rules, we construct the tree until generator Node 13 is included. The critical subgraph contains all generator nodes and consists of all paths from the generator nodes to the root node. In Figure 4, the critical Subgraph 1 is composed of paths (1, 2, 5) and (1, 2, 4, 12, 13). Figure 5 presents the 30-node graph in which the critical subgraphs associated with all coherent generator sets are marked in bold.  
The island \(G_{k}\) is constructed from the critical subgraph \(k\) by adding the remaining load nodes that are not included by the critical subgraphs. At the beginning, we denote the \(k\)-th island by \(G_{k}(0)\), which is equivalent to the critical subgraph \(k\). The set of nodes in \(G_{k}(0)\), denoted by \(V_{k}(0)\) is called the Layer 0 nodes of \(G_{k}\). The remaining node adjacent to any node in \(V_{k}(0)\) is called the Layer 1 node of \(G_{k}\). In Figure 5, the sets of Layer 1 nodes of \(G_{1}\) and \(G_{2}\) are { 3, 7, 14, 15, 16} and {7, 10, 28}, respectively.  
Figure 4: The tree associated with the coherent generator Set 1, where generator Node 1 is the root node and the critical subgraph is highlighted by bold lines.  
Next, we generate \(G_{k}(1)\) by assigning the Layer 1 nodes to \(G_{k}(0)\). If a node is a Layer 1 node of multiple islands (e.g., load Node 7 in Figure 5), we assign it to the island, such that the resultant total power imbalance of all islands is minimal. Figure 6 shows the 30-node graph in which \(G_{1}(1)\) and \(G_{2}(1)\) are marked in bold, and Load 7 is included in \(G_{1}(1)\). The remaining nodes are {17, 18,...  
Finally, we simplify the initial solution by merging the leaf load nodes into their adjacent load nodes or generator nodes. For the graph in Figure 7, we can merge load Nodes 29 and 30 into load Node 27, and combine Node 26 with Node 25.