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.