  Power system restoration is an essential activity for grid resilience, where
grid operators restart generators, re-establish transmission paths, and restore
loads after a blackout event. With a goal of restoring electric service in the
shortest time, the core decisions in restoration planning are to partition the
grid into sub-networks, each of which has an initial power source for
black-start (called sectionalization problem), and then restart all generators
in each network (called generator startup sequencing problem or GSS) as soon as
possible. Due to the complexity of each problem, the sectionalization and GSS
problems are usually solved separately, often resulting in a sub-optimal
solution. Our paper develops models and computational methods to solve the two
problems simultaneously. We first study the computational complexity of the GSS
problem and develop an efficient integer linear programming formulation. We
then integrate the GSS problem with the sectionalization problem and develop an
integer linear programming formulation for the parallel power system
restoration (PPSR) problem to find exact optimal solutions. To solve larger
systems, we then develop bounding approaches that find good upper and lower
bounds efficiently. Finally, to address computational challenges for very large
power grids, we develop a randomized approach to find a high-quality feasible
solution quickly. Our computational experiments demonstrate that the proposed
approaches are able to find good solutions for PPSR in up to 2000-bus systems.
