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

Abstract

For a given undirected graph G=(V,E) with a non-negative weight function w:E→R+ and subsets (formula presented) of V, the Group Steiner Tree (GST) problem consists of constructing a tree T=(VT,ET) with minimal cost, where (formula presented), 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.