Multiparent path relinking. An application to the power dominating set problem

  • We propose a reference framework to apply the multiparent path relinking (MPR) methodology. MPR is an extension of path relinking (PR) that has been proposed and described but, to the best of our knowledge, it has never been applied. PR is a trajectory-based neighborhood search strategy that explores paths that traverse pairs of solutions. PR has been widely used for search intensification purposes within metaheuristic implementations. To show how MPR can be embedded in more than one setting, our proposal consists of both employing MPR as a post-processing step in a greedy randomized adaptive search procedure (GRASP) and as the combination method in a scatter search (SS). We use the power dominating set problem (PDSP) as our testing platform because its difficulty and structure enable the design and assessment of various strategies. The PDSP seeks to find the minimum placement of measurement devices in an electrical network to monitor the entire system. Our computational experiments are designed to identify the contribution of each element of our proposed MRP implementations.

Download full text files

Export metadata

Additional Services

Share in Twitter Search Google Scholar
Metadaten
Author:R. Martín-SantamaríaORCiD, A. Martínez-GavaraORCiD, A. D. López-SánchezORCiD, M. LagunaORCiD
DOI:https://doi.org/https://doi.org/10.1007/s12532-025-00286-y
ISSN:1867-2949
Parent Title (English):Mathematical Programming Computation
Publisher:Springer Science and Business Media LLC
Document Type:Article
Language:English
Year of Completion:2025
Volume:17
Issue:4
Page Number:21
First Page:759
Last Page:779
Mathematical Programming Computation :MPC 2025 - Issue 4
Verstanden ✔
Diese Webseite verwendet technisch erforderliche Session-Cookies. Durch die weitere Nutzung der Webseite stimmen Sie diesem zu. Unsere Datenschutzerklärung finden Sie hier.