Solving the Steiner Tree Problem in graphs with Variable Neighborhood Descent

The Steiner Tree Problem (STP) is an important problem in combinatorial optimization which has numerous applications, ranging from the design of (very large) integrated circuits to computer networking, evolution theory in biology and more [8]. There are plenty variants of the STP which can be found in [7]. The common part between different variants is the requirement to connect a set of objects with the shortest interconnect possible. In this paper, we investigate the general STP in graphs. As the STP is N P-hard [10], most of the work in the literature focuses on non-exact approaches.