Greedy Randomized Adaptive Search Procedures For The Steiner Problem In Graphs
Simone L. Martins, Pãnos M. Pardalos, Maurício G. C. Resende, Celso Carneiro Ribeiro, Celso, C. Ribeiro · 1999
. We describe four versions of a Greedy Randomized Adaptive Search Procedure (GRASP) for finding approximate solutions of general instances of the Steiner Problem in Graphs. Di#erent construction and local search algorithms are presented. Preliminary computational results with one of the versions on a variety of test problems are reported. On the majority of instances from the OR-Library, a set of standard test problems, the GRASP produced optimal solutions. On those that optimal solutions were not found, the GRASP found good quality approximate solutions. 1. Introduction Posed independently by Hakimi [21] and Levin [30], the Steiner problem in graphs (SPG) consists in connecting a subset of given nodes on a graph with the minimum cost tree. The SPG has also many equivalent formulations as an integer program [22] or as a continuous nonconvex global optimization problem [26]. Karp [25] showed earlier that the SPG decision problem is NP-complete in general. Even for some restrictions li...