The restoration of a power system after an extended blackout starts around units with enhanced technical capabilities, referred to as black start units (BSUs). We examine the planning problem of optimally allocating these units on the grid subject to a budget constraint. We present a mixed integer programming model based on current literature in power systems. Binary variables are associated with the allocation of BSUs and with the energization state of buses, branches, and generators of the power system over a time horizon. We extract a substructure of the feasible region which imposes the requirement that each island that appears during the restoration process must contain at least one operational generator. We discuss reformulations for this requirement and introduce a family of exponentially many, polynomially separable, valid inequalities to strengthen the formulation. Under simplifying assumptions, we show that some of the constraints we introduced are facet defining. We perform experiments to examine the difference in strength between formulations and the computational times to solve the problem to near optimality for multiple synthetic power system instances with up to 2000 buses. We illustrate a use case of the model. We conclude by suggesting extensions of the current work for future research.