UC Berkeley

In this dissertation we develop models, solution techniques, and derive policy implications for a number of important applications in improving power system resilience and flexibility: black start allocation and power system restoration, optimal islanding, stochastic unit commitment and flexible wind dispatch. The models we employ are predominantly mixed integer programs (MIPs), i.e. optimization problems in which some of the variables must take integer values. These problems are NP-hard in general, so there is no guarantee that we will be able to obtain solutions within acceptable time and accuracy as the scale of the problem increases. For that reason, we also develop or utilize specialized computational techniques, which broadly fall into one of the following categories: decomposition algorithms that exploit the problem structure (sparsity), reformulations of the problem constraints, and customized heuristics.

We start by exploring the problem of restoring the normal operation of the power system after a blackout. The restoration of the system builds around specific units with the ability to start autonomously (black start units). We formulate a planning problem for deciding the allocation of these units on the grid - black start allocation (BSA) - in an optimal way, while simultaneously optimizing over the possible restoration plans. We include, among others, considerations for thermal limits of lines, alleviating overvoltages, and constraints to model the startup curves of generators. Due to the size and complexity of the resulting MIP, commercial solvers are unable to tackle it directly. We construct a randomized heuristic based on linear programming relaxations of the optimization problem and an understanding of the underlying physics of the power grid to aid the solvers. The heuristic execution is parallelized and implemented on a high-performance computing environment. We are able to obtain solutions with optimality guarantees within reasonable times for test power systems with a few hundred buses.

We proceed to extract a substructure of the feasible region from any problem in power systems that employs reconfiguration of the physical topology (i.e. switching on/off of generators, branches, and buses): each energized island in the power system needs to contain at least one energized generator. We explore reformulations that describe the feasible region corresponding to this requirement. We employ two families of valid inequalities to strengthen the formulation, both exponential in size, but separable in polynomial time. We study polyhedral properties of the integer hull and the strength of some of these inequalities under simplifying assumptions. We proceed to conduct computational experiments for two problems in which the substructure appears: the optimal islanding problem and a simplified version of the BSA problem. We are able to observe significant computational benefits by using suitable reformulations for both problems. Finally, we describe an approach to obtain solutions with an optimality guarantee for a simplified model of BSA in a synthetic test case with 2000 nodes representative of Texas.

We extend the modeling framework of the BSA problem to accommodate for uncertainty in the power outages. Specifically, we consider optimal allocations of the black start units over a number of scenarios of partial or total outages. These scenarios may also include irreparable damage caused to components of the system. The resulting stochastic mixed integer program exhibits sparsity, so we employ a decomposition algorithm by scenario to solve instances of the problem.

We then return to the optimal islanding problem to examine it in more detail. We observe that, despite the formulation improvements, the branch and cut algorithm is still fairly slow for an online application of that scale, which requires to act within seconds to prevent a cascaded outage of the system. For that reason, we propose a heuristic based on a reformulation of the optimization into a problem in graph theory. We utilize an algorithm to obtain heuristic solutions with high computational efficiency and good quality compared to state-of-the-art techniques.

To conclude this dissertation, we introduce a framework for evaluating the cost of priority dispatch for wind power. Renewable generation is commonly considered a must-take resource in power systems, despite the technical capabilities of current wind turbines to dispatch at levels lower than their available output. The cost of that policy compared to one that instead optimizes over the available wind output is evaluated for a reduced California system, by employing a two-stage stochastic program for stochastic unit commitment. A scenario decomposition algorithm for the resulting large-scale MIP, parallelized on a high-performance computing environment, enables us to obtain near optimal solutions and calculate the difference in cost between the two policies.