Solving the prize-collecting Euclidean Steiner tree problem

Abstract

The prize‐collecting Euclidean Steiner tree (PCEST) problem is a generalization of the well‐known Euclidean Steiner tree (EST) problem. All points given in an EST problem instance are connected by the shortest possible network in a solution. A solution can include additional points called Steiner points. A PCEST problem instance differs from an EST problem instance by the addition of weights for each given point. A PCEST solution connects a subset of the given points in order to maximize the net value of the network (the sum of the selected point weights, less than the length of the network). We present an algorithmic framework for solving the PCEST problem. Included in the framework are efficient methods to determine subsets of points that must be in every solution, and subsets of points that cannot be in any solution. Also included are methods to generate and concatenate full Steiner trees.