Computational Complexity of Electrical Power System Problems

Abstract

The study of the computational complexity of real-world applications, although theoretical, can provide many pragmatic outcomes. For example, demonstrating that some types of algorithms cannot exist to solve the problem; the creation of challenging benchmark examples; and new insights into the underling structure and properties of the problem. In this thesis, we study the computational complexity of several important problems in the application of electrical power systems.

Knowledge of the current state of the power system is important for power network operators. This helps, for example, to predict if the network is trending towards an undesirable state of operation, or if a power line is working at its operational limits. The state of a power system is determined by the demand, the generation and the bus voltage magnitudes and phase angles. The demand of loads can be reliably estimated via forecasts, historic records and/or measurements and the operators of generators report the generation values. Given generation and demand values, the voltage magnitudes and phase angles can be computed. This is what is called the Power Flow problem. Cost for generating power often varies from generator to generator. In the Optimal Power Flow problem, the aim is to find the cheapest generation dispatch, such that the forecast demand can be satisfied. Disasters, such as storms or floods, and operator errors have to potential to destroy parts of the network. This can make it impossible to satisfy all the demand. In the Maximum Power Flow problem, the aim is to find a generation dispatch that can satisfy as much demand as possible.

In this thesis, we provide the proofs that the Maximum Power Flow, Optimal Power Flow and the Power Flow problem are NP-hard for: radial networks in the Alternating Current power flow model and planar networks in the Linear AC Approximation (DC) power flow model with line switching. Furthermore, we show that there does not exist a polynomial approximation algorithm for the Optimal Power Flow problem in any of these settings. We also study the complexity of the Lossless-Sin AC Approximation power flow model, showing that the Maximum Power Flow and Optimal Power Flow problem are strongly NP-hard for planar networks. Show more