Efficient heuristics for the Steiner forest problem

Murilo Stockinger

doi:10.1111/itor.70250

Return

Efficient heuristics for the Steiner forest problem

2026-09-19

Murilo Stockinger *

Isabel Rosseti

Simone de Lima Martins

Luidi Simonetti

Alexandre Plastino

DOI：10.1111/itor.70250

Original

Save

View PDF

Abstract

En 中文

Let be a connected undirected graph, a set of nodes, a set of edges, , and . Given a non-negative weight function associated with its edges, a set of terminal sets , the Steiner forest problem (SFP) consists of finding a subset of edges with the minimal cost such that all vertices of each (for ) lie in the same connected component in the graph induced by . In this work, as a first contribution, we propose a constructive algorithm for the SFP. Computational experiments on literature instances showed that the results obtained by the constructive algorithm outperformed the state-of-the-art primal-dual algorithm. Furthermore, as a second contribution, we present two heuristics to solve the SFP: the first, named GRASP-SFP, based on the GRASP metaheuristic, and the second, called MDM-GRASP-SFP, which incorporates a data mining component on GRASP-SFP. In most test instances provided in the literature, the results obtained by the two proposed algorithms tied for both best and average solution costs. Due to this fact, we generated more challenging SFP instances and the results reached by the proposed hybrid data mining heuristic improved upon those obtained by the original GRASP approach.

Keywords:

Steiner forest problem

GRASP

data mining

hybrid heuristics

metaheuristics

AI Summary

Key information extracted from the uploaded paper, including a brief overview, abstract, background, key highlights, visual analysis, and future outlook.