Article ID: | iaor2009608 |
Country: | Netherlands |
Volume: | 14 |
Issue: | 1 |
Start Page Number: | 69 |
End Page Number: | 93 |
Publication Date: | Feb 2008 |
Journal: | Journal of Heuristics |
Authors: | Golden Bruce, Raghavan S., Stanojevi Daliborka |
Keywords: | graphs |
We introduce the prize-collecting generalized minimum spanning tree problem. In this problem a network of node clusters needs to be connected via a tree architecture using exactly one node per cluster. Nodes in each cluster compete by offering a payment for selection. This problem is NP-hard, and we describe several heuristic strategies, including local search and a genetic algorithm. Further, we present a simple and computationally efficient branch-and-cut algorithm.