Abstract

In the era of dynamic smart grid with fluctuating demands and uncertain renewable energy supplies, it is crucial to continuously optimize the operational cost and performance of electric power grid, while maintaining its state within the stable operating limits. Nonetheless, a major part of electric power grid consists of alternating current (AC) electric power systems, which exhibit complex behavior with nonlinear operating constraints. The optimization of AC electric power systems with dynamic demands and supplies is a very challenging problem for electrical power engineers. The hardness of optimization problems of AC electric power systems stems from two issues: (1) non-convexity involving complex-valued entities of electric power systems, and (2) combinatorial constraints involving discrete control variables. Without proper theoretical tools, heuristic methods or general numerical solvers had been utilized traditionally to tackle these problems, which do not provide theoretical guarantees of the achieved solutions with respect to the true optimal solutions. There have been recent advances in applying convex relaxations to tackle non-convex problems of AC electric power systems. On the other hand, discrete combinatorial optimization is rooted in theoretical computer science, which typically considers linear constraints, instead of those non-linear constraints in AC electric power systems. To bridge power systems engineering and theoretical computer science, this monograph presents a comprehensive study of combinatorial optimization of AC electric power systems with (inelastic) discrete demands. The main idea of this monograph is to draw on new extensions of discrete combinatorial optimization with linear constraints, like knapsack and unsplittable flow problems. We present approximation algorithms and inapproximability results for various settings from (1) basic single-capacitated AC electric power systems, to (2) constant-sized AC electric grid networks with power flows, and (3) scheduling of AC electric power. This monograph aims to establish a foundation for the inter-disciplinary problems of power systems engineering and theoretical computer science.

Combinatorial Optimization of Alternating Current Electric Power Systems

The electric power grid which has been an indispensable part of our society is being put under increasing pressure to meet the demands of a major surge in global energy consumption. As a result, the power grid needs to undergo transformations to meet the new challenges for a more sustainable society. One of these transformations is the need for continuous optimization in the smart grid so that it can react rapidly to dynamic situations in presence of fluctuating demands and uncertain renewable energy. In the past, the operations of power grid relied on careful a-priori planning, under the assumptions of static demands and predictable circumstances. In the era of dynamic smart grid, self-optimization with adaptive control is more crucial to its operations. Many of the ideas developed by the theoretical computer science community can be applied in such cases.

This monograph establishes an interdisciplinary bridge between power systems engineering and theoretical computer science by relating the practical and challenging problems in electric power systems with the modern theoretical tools from computer science. The proper understanding of these hard problems in electric power systems can advance the frontiers of both communities.

This monograph introduces Power System Engineers to the concepts and results of approximation algorithms, and applies them to solve electric power systems problems as well as providing Computer Scientists with an exposition of a class of challenging combinatorial problems in electric power systems.