Optimal Sensor Placement in Power Grids: Power Domination, Set Covering, and the Neighborhoods of Zero Forcing Forts

Autor:	Smith, Logan A., Hicks, Illya V.
Rok vydání:	2020
Předmět:	Computer Science - Data Structures and Algorithms Computer Science - Discrete Mathematics Mathematics - Combinatorics Mathematics - Optimization and Control G.2.2 G.2.1 F.2.2
Druh dokumentu:	Working Paper
Popis:	To monitor electrical activity throughout the power grid and mitigate outages, sensors known as phasor measurement units can installed. Due to implementation costs, it is desirable to minimize the number of sensors deployed while ensuring that the grid can be effectively monitored. This optimization problem motivates the graph theoretic power dominating set problem. In this paper, we propose a novel integer program for identifying minimum power dominating sets by formulating a set cover problem. This problem's constraints correspond to neighborhoods of zero forcing forts; we study their structural properties and show they can be separated, allowing the proposed model to be solved via row generation. The proposed and existing methods are compared in several computational experiments in which the proposed method consistently exhibits an order of magnitude improvement in runtime performance. Comment: 26 pages, 7 figures
Databáze:	arXiv
Externí odkaz:	http://arxiv.org/abs/2006.03460 Zobrazit plný text záznamu View this record from Arxiv