Generating lower bounds for the prize collecting Steiner problem in graphs

Given an undirected graph G with nonnegative edges costs and nonnegative vertex penalties, the prize collecting Steiner problem in graphs (PCSPG) seeks a tree of G with minimum weight. The weight of a tree is the sum of its edge costs plus the sum of the penalties for those vertices not spanned by the tree. In this paper we present an integer programming formulation of the PCSPG and some tests that attempt to reduce problem input size. Computational experiments have been carried out to evaluate the strength of the formulation through its linear programming relaxation. For most instances tested, linear programming relaxation solutions turned out to be integral.