Journal article

Solving the prize-collecting Euclidean Steiner tree problem

David Whittle, Marcus Brazil, Peter A Grossman, J Hyam Rubinstein, Doreen A Thomas

International Transactions in Operational Research | Wiley | Published : 2020


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 eff..

View full abstract


Funding Acknowledgements

David Whittle is the grateful recipient of the 2015 Gilbert Rigg Scholarship, which supported his graduate research in underground mine plan optimization. In addition, David was awarded the 2016 John Collier Scholarship to support his research-related travel.