Lagrangian Relaxations for the Prize-Collecting Steiner Tree Problem

Abstract

In this thesis we look at the NP-hard Prize-Collecting Steiner Tree Problem (PCSTP). We show an application within biology, where the PCSTP is used to identify coregulated genes which are differently expressed for diffuse stomach cancer with and without signet ring cells. Identifying these genes can help to create better treatment for stomach cancer.We use Lagrangian relaxation to solve the PCSTP. Two relaxations are tested, one creating tights bounds and one weak bounds. For the tightest relaxation we test two heuristic methods for creating primal bounds, and for the unrooted PCSTP we find the optimal solution for all but one of the instances with both heuristics. A multiple rooted generalization of the PCSTP is introduced, and shown to be easily handled by the formulations. We do not obtain as tight bounds as for the corresponding unrooted instances.