Combinatorial Optimization of Alternating Current Electric Power Systems

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.