A matheuristic algorithm for the Prize-collecting Steiner Tree Problem

The Prize-collecting Steiner Tree Problem (PCSTP) is a well studied problem in combinatorial optimization. It has a wide range of applications in the literature, for instance in fiber optics such as gas distribution and district heating. In this study, we focus on its application in functional analysis of genes on bio-genetic graphs. In bio-genetics its extremely possible to have a huge graphs to interpret. Since the PCSTP is NP-hard, it is time consuming to obtain solutions for large instances. Thus, there is a need for efficient and fast heuristic algorithms to discover the hidden knowledge behind the vast bio-genetic networks. We propose a matheuristic composed of heuristic clustering algorithm and existing mixed integer liner programming to solve PCSTP. We evaluated the performance of our matheuristic on available real-world benchmark instances from the biology and compared it with existing heuristic approach in the literature. With respect to heuristic results, we obtained solutions with similar or better objective function values. On the other hand the existing heuristic solved the benchmark instances with smaller running time compared to proposed matheuristic.