VNS-Based Matheuristic Approach to Group Steiner Tree with Problem-Specific Node Release Strategy

For a given undirected graph \(G = (V, E)\) with a non-negative weight function \(w : E \rightarrow \mathbb {R}_{+}\) and subsets \(G_1, \dots , G_k\) of V, the Group Steiner Tree (GST) problem consists of constructing a tree \(T = (V_T, E_T)\) with minimal cost, where \(V_T \subseteq V\) , \(E_T \subseteq E\) , and T spans at least one node from each of the groups. We develop a VNS-based metaheuristics approach for solving the GST problem. Our main contribution is that we propose a new problem-specific node release strategy that mimics the steps of a VNS-based heuristic. Instead of exploring different neighborhoods by combinatorially enumerating neighboring solutions, as in classical local search, we use a provably good Integer Linear Programming (ILP) formulation to solve a sequence of subproblems of the original problem. Our approach leads to an improvement over the state-of-the-art Gurobi solver both in terms of quality and runtime of the instances available in the literature.