Algorithmic expedients for the prize collecting Steiner tree problem

Abstract

This paper investigates the Prize Collecting Steiner Tree Problem (PCSTP) on a graph, which is a generalization of the well-known Steiner tree problem. Given a root node, edge costs, node prizes and penalties, as well as a preset quota, the PCSTP seeks to find a subtree that includes the root node and collects a total prize not smaller than the specified quota, while minimizing the sum of the total edge costs of the tree plus the penalties associated with the nodes that are not included in the subtree. For this challenging network design problem that arises in telecommunication settings, we present two valid 0-1 programming formulations and use them to develop preprocessing procedures for reducing the graph size. Also, we design an optimization-based heuristic that requires solving a PCSTP on a specific tree-subgraph. Although, this latter special case is shown to be NP-hard, it is effectively solvable in pseudo-polynomial time. The worst-case performance of the proposed heuristic is also investigated. In addition, we describe new valid inequalities for the PCSTP and embed all the aforementioned constructs in an exact row-generation approach. Our computational study reveals that the proposed approach can solve relatively large-scale PCSTP instances having up to 1000 nodes to optimality.