EURO 2025 Leeds
Abstract Submission

2067. Multiparent Path Relinking for the Power Dominating Set problem

Invited abstract in session TC-15: Heuristic Search 3, stream Combinatorial Optimization.

Tuesday, 12:30-14:00
Room: Esther Simpson 1.08

Authors (first author is the speaker)

1. Raúl Martín-Santamaría
Departamento de Informática y Estadística, Universidad Rey Juan Carlos
2. Anna Martínez-Gavara
Estadística i Investigació Operativa, Universitat de València
3. Ana Dolores López-Sánchez
Economía, Métodos Cuantitativos e Historia Económica, Universidad Pablo de Olavide
4. Manuel Laguna
Leeds School of Business, University of Colorado Boulder

Abstract

Path Relinking (PR) is a trajectory-based metaheuristic originally introduced as a long-term memory mechanism within Tabu Search (TS). It explores trajectories that connect elite solutions identified during the search process. PR has also been used as an intensification strategy in hybridizations with the Greedy Randomized Adaptive Search Procedure (GRASP) and as a combinatorial method in Scatter Search (SS).
In this talk, we present an extension of PR known as Multi-Parent Path Relinking (MPR), initially proposed by Glover et al. (2000) but, to the best of our knowledge, not yet implemented in practice. We introduce a reference framework for integrating MPR into GRASP and SS, demonstrating its potential to enhance solution quality.
To evaluate its performance, we focus on the Power Dominating Set Problem (PDSP), which seeks the minimal set of nodes in a network to achieve complete system monitoring. The complex structure of the PDSP presents a challenging test bed for assessing various metaheuristic strategies. Through extensive computational experiments, we analyze the contributions of each component within our MPR implementations, demonstrating its effectiveness in improving metaheuristic performance.

Glover, F., Laguna, M., Martí, R.: Fundamentals of scatter search and path relinking.
Control and Cybernetics 29, 653–684 (2000)

Keywords

Status: accepted

Back to the list of papers