Approximation algorithms and mechanism design for power systems

dc.contributor.advisorNikolova, Evdokia
dc.contributor.committeeMemberde Veciana, Gustavo
dc.contributor.committeeMemberShakkottai, Sanjay
dc.contributor.committeeMemberZhu, Hao
dc.contributor.committeeMemberGupta, Swati
dc.creatorKhodabakhsh, Ali
dc.creator.orcid0000-0001-9894-3565
dc.date.accessioned2021-07-16T21:12:25Z
dc.date.available2021-07-16T21:12:25Z
dc.date.created2021-05
dc.date.issued2021-04-02
dc.date.submittedMay 2021
dc.date.updated2021-07-16T21:12:25Z
dc.description.abstractIn 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.
dc.description.departmentElectrical and Computer Engineeringeng
dc.format.mimetypeapplication/pdf
dc.identifier.urihttps://hdl.handle.net/2152/86864
dc.identifier.urihttp://dx.doi.org/10.26153/tsw/13815
dc.language.isoen
dc.subjectApproximation algorithms
dc.subjectMechanism design
dc.subjectPower systems
dc.titleApproximation algorithms and mechanism design for power systems
dc.typeThesis
dc.type.materialtext
thesis.degree.departmentElectrical and Computer Engineering
thesis.degree.disciplineElectrical and Computer Engineering
thesis.degree.grantorThe University of Texas at Austin
thesis.degree.levelDoctoral
thesis.degree.nameDoctor of Philosophy

Access full-text files

Original bundle

Now showing 1 - 1 of 1
Loading...
Thumbnail Image
Name:
KHODABAKHSH-DISSERTATION-2021.pdf
Size:
5.47 MB
Format:
Adobe Portable Document Format

License bundle

Now showing 1 - 2 of 2
No Thumbnail Available
Name:
PROQUEST_LICENSE.txt
Size:
4.45 KB
Format:
Plain Text
Description:
No Thumbnail Available
Name:
LICENSE.txt
Size:
1.84 KB
Format:
Plain Text
Description: