The Prize-Collecting Steiner Tree Problem

by Ivana Ljubic
University of Vienna
Intro: Let G = (V,E, c, p) be an undirected graph, with the vertices V associated with non-negative profits p, and with the edges E associated with non-negative costs c. The graph may correspond to the local street map, for example, with the edges representing street segments and vertices representing street intersections and the location of potential customers. The profit p associated with a vertex is an estimate of the potential gain of revenue caused by that customer being connected to the network and receiving its service. Vertices corresponding to street intersections have profit zero. The cost c associated with an edge is the cost of establishing the connection, i.e., of laying the pipe or cable on the corresponding street segment.

Definition: The Linear Prize-Collecting Steiner Tree problem (PCST) consists of finding a connected subgraph T = (V' ,E' ) of G, that maximizes profit(T) which is defined as the sum of all node-prizes taken into the solution minus the costs of the edges needed to establish the network.

Alternatively, one can minimize the edge-costs for establishing the network plus the penalties of the vertices outside of the solution.
[Example] [Example]
Input graph: hollow circles are customers A feasible but not optimal PCST solution


DOWNLOAD
Related Applications:
  • k-CARDINALITY TREES: using an extension of the dhea-code, we are able to solve all the instances of the KCT-LIB to provable optimality. See our paper.
  • BIOINFORMATICS: The dhea code has been successfully used for
    • finding functional modules in cancer interactome data. For further details see HEINZ library and a web-page of Gunnar Klau.
    • revealing the hidden components in regulatory and signaling networks by integrating proteomics, transcriptome and interactome Data, see SteinerNet
Licensing:
2003 - 2013
dhea-team
    This code is free software. If you use it in your research, give the credits to our Mathematical Programming publication stated above.

    Part of the dhea code makes use of the following software, whose licences you will need in order to be able to run the dhea-code: The dhea-code has been developed with academic LEDA/CPLEX licenses for non-commercial purposes only.
Benchmark instances:
  • Instances from Mauricio Resende's web-page:
  • Group E: Download (5.8MB)
  • Real-world instances: Cologne -- these are rooted instances with the node 1 taken as the root. Set parameter "rooted" to "1", for solving them. Instances are already preprocessed real-world inputs, and the relevant data can be found in "out" subfolders.
  • After preprocessing described in Ljubic et al. (2006): Download groups C, D, E, K, P (4.5MB). Due to vertex-elimination and fixing, optimal solution values for reduced instances are different from the original ones.
Bibliography:
  1. A.S. da Cunha, A. Lucena, N. Maculan, and M.G.C. Resende: A relax-and-cut algorithm for the prize-collecting Steiner problem in graphs. Discrete Applied Mathematics. article in press. (2008), doi:10.1016/j.dam.2008.02.014
  2. E. Uchoa: Reduction tests for the prize-collecting Steiner problem. Oper. Res. Lett. 34(4): 437-444. 2006.
  3. I. Ljubic, R. Weiskircher, U. Pferschy, G. Klau, P. Mutzel, and M. Fischetti: An algorithmic framework for the exact solution of the prize-collecting Steiner tree problem. Mathematical Programming, Series B, 105(2-3):427-449, 2006.
  4. O. Chapovska, A. P. Punnen: Variations of the prize-collecting Steiner tree problem. Networks 47(4): 199-205. 2006
  5. A. Moser: Finding Provably Optimal Solutions for the (Prize Collecting) Steiner Tree Problem. Master Thesis. Vienna University of Technology, 2005.
  6. G.W. Klau, I. Ljubic, A. Moser, P. Mutzel, P. Neuner, U. Pferschy, and R. Weiskircher. Combining a memetic algorithm with integer programming to solve the prize-collecting Steiner tree problem. In K. Deb, editor, Proceedings of the Genetic and Evolutionary Computation Conference (GECCO-2004), volume 3102 of LNCS, pages 1304-1315. Springer-Verlag, 2004.
  7. A. Lucena, M. G. C. Resende: Strong lower bounds for the prize collecting Steiner problem in graphs. Discrete Applied Mathematics 141(1-3): 277-294. 2004.
  8. S. A. Canuto, M. G. C. Resende, and C. C. Ribeiro. Local search with perturbations for the prize-collecting Steiner tree problem in graphs. Networks, 38:50-58, 2001.
  9. D. S. Johnson, M. Minkoff, and S. Phillips. The prize-collecting Steiner tree problem: Theory and practice. In Proceedings of 11th ACM-SIAM Symposium on Discrete Algorithms, pages 760-769, San Francisco, CA, 2000.
  10. S. Engevall, M. Göthe-Lundgren, and P. Väarbrand. A strong lower bound for the node weighted Steiner tree problem. Networks, 31(1):11-17, 1998.
  11. M. X. Goemans and D. P.Williamson. The primal-dual method for approximation algorithms and its application to network design problems. In D. S. Hochbaum, editor, Approximation algorithms for NP-hard problems, pages 144-191. P. W. S. Publishing Co., 1996.
  12. D. Bienstock, M. X. Goemans, D. Simchi-Levi, and D. Williamson. A note on the prize-collecting traveling salesman problem. Mathematical Programming, 59:413-420, 1993.
Contact: ivana.ljubic @univie.ac.at