Revisiting search methods for the Bounded-Diameter Minimum Spanning Tree Problem
Rogério M. Nepomuceno, Rodrigo Lamblet Mafort, Fábio Protti, Isabel Rosseti, Luidi Gelabert Simonetti, Edoarda Vallim · RAIRO - Operations Research · 2025
The Bounded-Diameter Minimum Spanning Tree Problem (BDMSTP) is defined as follows: Given a graph G where each edge xy has a positive cost w xy the goal is to find an optimal spanning tree of G whose diameter does not exceed a prescribed positive integer D ≤2. Applications of the BDMSTP appear in telecommunication network and fiber optic projects, data compression problems, and distributed systems design. This work revisits search methods for the BDMSTP and proposes alternative combinations of local search moves, intending to select efficient sets of moves and improve the quality of the solutions found in the literature. For small 50-and 100-node instances from the widely-used OR-Library, we obtain exact solutions whose optimal values were so far unknown. Having solved these easier cases, we can then concentrate our efforts on solving more challenging OR-Library graph instances with 250, 500, and 1000 nodes. The process of selecting efficient sets of search moves is done by encapsulating different local search versions (based on the Variable Neighborhood Descent method) in an ILS approach. Some new neighborhoods are also proposed. Computational tests show that these neighborhoods allowed the proposed ILS approach to obtain better results than those presented in the literature.