New computational approaches for the power dominating set problem: Set covering and the neighborhoods of zero forcing forts
New computational approaches for the power dominating set problem: Set covering and the neighborhoods of zero forcing forts
复制标题
DOI：
10.1002/net.22056
复制
发表时间：
2021-05
期刊：
影响因子：
2.1
通讯作者：
Logan A. Smith;Illya V. Hicks
中科院分区：
文献类型：
--
作者：
Logan A. Smith;Illya V. Hicks
为了监控整个电网的电气活动并减少停电，可以安装称为相量测量单元的传感器。由于实施成本的原因，期望在确保可以有效地监测电网的同时最小化部署的传感器的数量。这个优化问题激发了图论的幂控制集问题。在本文中，我们提出了一种方法来计算最小功率控制集通过一个集覆盖IP制定和一个新的约束生成过程。集合覆盖问题的约束对应于迫零邻域，我们研究了它们的结构特性，并表明它们可以通过延迟行生成来分离。此外，我们提供了几个计算增强，适用于我们的方法以及现有的方法。建议和现有的方法进行了评估，在几个计算实验。在许多较大的测试实例中，所提出的方法表现出一个数量级的运行时性能改善。
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 method for computing minimum power dominating sets via a set cover IP formulation and a novel constraint generation procedure. The set cover problem's constraints correspond to neighborhoods of zero forcing forts; we study their structural properties and show they can be separated with delayed row generation. In addition, we offer several computation enhancements which be be applied to our methodology as well as existing methods. The proposed and existing methods are evaluated in several computational experiments. In many of the larger test instances considered, the proposed method exhibits an order of magnitude runtime performance improvement.