A fast heuristic for the prize-collecting Steiner tree problem

The Prize-Collecting Steiner Tree Problem (PCSTP) is a generalized version of the Steiner Tree Problem. PCSTP is well known and well studied problem in Combinatorial Optimization. Since PCSTP is NP-hard, it is computationally costly to achieve solutions for large instances. However, many real life network problems come with a wide range of variables and large instance sizes. Therefore, there is a need for efficient and fast heuristic algorithms to discover the hidden knowledge behind vast networks. There exists a fast heuristic algorithm for the Steiner Tree Problem in the literature, which is based on Minimum Spanning Trees. In this paper, we propose to extend the existing heuristic algorithm to solve PCSTP. The performance of the extended heuristic (MST-PCST) is evaluated on available benchmark instances from the literature. We also test MST-PCST on randomly generated huge graph instances with up to 40000 nodes and 120000 edges. We report the average gap percentage between the solutions of MST-PCST and existing solution approaches in the literature. Results show that overall performance of MST-PCST is promising with tolerable gap percentage and reasonable running time on larger instances. It has a significantly faster running time when graphs scale up which can shed light on large real world network instances.