Combinatorial Optimization of Alternating Current Electric Power Systems
Sid Chi-Kin Chau, Khaled Elbassioni, Majid Khonji
Foundations and Trends in Electric Energy Systems, Now Publishers Inc.
ISBN: 978-1-68083-514-4 [Publication Date: Dec 2018]
Download a preprint , and tutorial slides
Summary: 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 non-linear 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.
Table of Contents:
- Chapter 1: Introduction
- Section 1.1: Need for Optimization in Smart Power Grid
- Section 1.2: Basics of AC Electric Power Systems
- Section 1.3: Basics of Combinatorial Optimization
- Chapter 2: Single-capacitated AC Electric Power Systems
- Section 2.1: Preliminaries of Knapsack Problem
- Section 2.2: Greedy Approximation Algorithm
- Section 2.3: PTAS
- Section 2.4: Resource-augmented FPTAS
- Chapter 3: Constant-sized AC Electric Power Networks
- Section 3.1: Preliminaries of OPF
- Section 3.2: SOCP Relaxation of OPF
- Section 3.3: PTAS
- Section 3.4: Greedy Approximation Algorithm
- Chapter 4: Scheduling of AC Electric Power
- Section 4.1: Preliminaries of Multi-Choice Knapsack Problem
- Section 4.2: PTAS
- Section 4.3: Resource-augmented FPTAS
- Chapter 5: Hardness Results
- Section 5.1: Absence of FPTAS
- Section 5.2: Hardness of CKP
- Section 5.3: Hardness of OPF with Voltage Constraint
- Section 5.4: Hardness of OPF with Capacity Constraint
- Chapter 6: Simulation Studies
- Section 6.1: Simulation Settings
- Section 6.2: Single-capacitated AC Electric Power Systems
- Section 6.3: Constant-Sized AC Electric Power Networks
- Section 6.4: Scheduling of AC Electric Power
- Chapter 7: Future Directions and Conclusion
- Section 7.1: Scalable Algorithms for Large Power Networks
- Section 7.2: Online Algorithms
- Section 7.3: Truthful Mechanisms
This monograph draws on my related publications in ACM Trans. on Economics and Computation, IEEE Trans. on Smart Grid, IEEE Trans. on Control of Network Systems, IEEE Trans. on Power Systems, Theoretical Computer Science, Annals of Operations Research, Autonomous Agents and Multiagent Systems (AAMAS).