Efficient heuristics for the Steiner forest problem

Abstract

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.