Approximation algorithms and mechanism design for power systems

In real life, many combinatorial optimization problems are solved by simple algorithms (e.g., greedy, local search, thresholding, etc.) without any provable guarantees on the performance of the returned solution compared to the optimal one. Even though theoretical computer scientists have established strong results for the performance of such algorithms in diverse settings, it is not always easy to match the real life application to one of those well-studied problems. That said, we also have power systems which is a rich source of combinatorial optimization problems. The combinatorial nature arises whether it is turning switches on or off, assigning generation to different sources, scheduling charging or discharging of electric vehicles, splitting loads between different phases, or installing equipment at certain locations of the grid. On top of the combinatorial nature, these applications usually entail another level of complexity due to the nonlinearity of their objective and/or constraints.

In this Ph.D. dissertation, I will try to bridge theoretical computer science and power systems by utilizing tools from approximation algorithms and mechanism design to provide rigorous guarantees for three problems in power systems. Contributing to the intersection of these two fields is important to both push the state-of-the-art approximation algorithms by introducing new problems that cannot be solved with existing techniques, as well as provide methods for both scalable and rigorous solutions to problems arising in real-world power systems.

In the first problem, the goal is to minimize the power loss in a distribution network via changing the on/off status of switches in the network. Bringing to bear recent advances in submodular optimization, we derive performance bounds for a simple local-search algorithm that has been used in practice for a long time. We then focus on special properties of the grid that let us develop tailored algorithms with improved performance guarantees. Finally, we use our insights from our theoretical analysis to propose a general heuristic for the network reconfiguration problem that is orders of magnitude faster than existing methods in the literature, while obtaining comparable performance.

In the second problem, we propose a novel way to use electric vehicles as dynamic energy storage for supporting the power grid, by discharging them at designated times and locations of need. We show that the underlying scheduling problem is NP-hard and propose various approximation algorithms with different performance guarantees.

Finally in the last problem, we study a mechanism design problem for a system operator who wants to optimally assign the demand to different energy generators. We study this as a dynamic procurement auction, in which the generators may go out of business if they are not frequently picked. Since this will increase the electricity price in the long term, the system operator has to design a mechanism that minimizes the overall cost via selecting different sources frequent enough to maintain the competition. We show how to obtain optimal thresholding mechanisms via a greedy approach.