Paper Info
Title
The Fixed Set Search Applied To The Power Dominating Set Problem
Abstract
In this article, we focus on solving the power dominating set problem and its connected version. These problems are frequently used for finding optimal placements of phasor measurement units in power systems. We present an improved integer linear program (ILP) for both problems. In addition, a greedy constructive algorithm and a local search are developed. A greedy randomised adaptive search procedure (GRASP) algorithm is created to find near optimal solutions for large scale problem instances. The performance of the GRASP is further enhanced by extending it to the novel fixed set search (FSS) metaheuristic. Our computational results show that the proposed ILP has a significantly lower computational cost than existing ILPs for both versions of the problem. The proposed FSS algorithm manages to find all the optimal solutions that have been acquired using the ILP. In the last group of tests, it is shown that the FSS can significantly outperform the GRASP in both solution quality and computational cost.
Year
DOI
Venue
2020
10.1111/exsy.12559
EXPERT SYSTEMS
Keywords
DocType
Volume
combinatorial optimization, dominating set, fixed set search, GRASP, power dominating set
Journal
37
Issue
ISSN
Citations 
6
0266-4720
2
PageRank 
References 
Authors
0.36
0
2
Name
Order
Citations
PageRank
Raka Jovanovic11218.70
Stefan Voß259246.77