DOWNLOAD

 dheacode is a branchandcut algorithm for solving the undirected prizecollecting Steiner tree problem. Main features of the algorithm are described in:
 I. Ljubic, R. Weiskircher, U. Pferschy, G. Klau, P. Mutzel, and M. Fischetti:
An algorithmic framework for the exact solution of the prizecollecting Steiner tree problem.
Mathematical Programming, Series B, 105(23):427449, 2006.
 Ivana Ljubic.
Exact and Memetic Algorithms for Two Network Design Problems.
PhD thesis, Faculty of Computer Science, Vienna University of Technology, November 2004.
 ExecutableFile for 64bit machines can be obtained HERE
 ExecutableFile for 32bit machines (Linux/UnixPlatform) can be obtained HERE
 User Manual

Benchmark instances:

 Instances from Mauricio Resende's webpage:
 Group E: Download (5.8MB)
 Realworld 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 realworld 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 vertexelimination and fixing, optimal solution values for reduced instances are different from the original ones.

Bibliography:

 A.S. da Cunha, A. Lucena, N. Maculan, and M.G.C. Resende:
A relaxandcut algorithm for the prizecollecting Steiner problem in graphs. Discrete Applied Mathematics. article in press. (2008), doi:10.1016/j.dam.2008.02.014
 E. Uchoa: Reduction tests for the prizecollecting Steiner problem. Oper. Res. Lett. 34(4): 437444. 2006.
 I. Ljubic, R. Weiskircher, U. Pferschy, G. Klau, P. Mutzel, and M. Fischetti:
An algorithmic framework for the exact solution of the prizecollecting Steiner tree problem.
Mathematical Programming, Series B, 105(23):427449, 2006.
 O. Chapovska, A. P. Punnen: Variations of the prizecollecting Steiner tree problem. Networks 47(4): 199205. 2006
 A. Moser: Finding Provably Optimal Solutions for the (Prize Collecting) Steiner Tree Problem. Master Thesis. Vienna University of Technology, 2005.
 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 prizecollecting Steiner tree problem. In K. Deb, editor, Proceedings of the Genetic
and Evolutionary Computation Conference (GECCO2004), volume 3102 of LNCS, pages 13041315. SpringerVerlag,
2004.
 A. Lucena, M. G. C. Resende: Strong lower bounds for the prize collecting Steiner problem in graphs.
Discrete Applied Mathematics 141(13): 277294. 2004.
 S. A. Canuto, M. G. C. Resende, and C. C. Ribeiro. Local search with perturbations for the prizecollecting Steiner tree
problem in graphs. Networks, 38:5058, 2001.
 D. S. Johnson, M. Minkoff, and S. Phillips. The prizecollecting Steiner tree problem: Theory and practice. In Proceedings
of 11th ACMSIAM Symposium on Discrete Algorithms, pages 760769, San Francisco, CA, 2000.
 S. Engevall, M. GötheLundgren, and P. Väarbrand. A strong lower bound for the node weighted Steiner tree problem.
Networks, 31(1):1117, 1998.
 M. X. Goemans and D. P.Williamson. The primaldual method for approximation algorithms and its application to network
design problems. In D. S. Hochbaum, editor, Approximation algorithms for NPhard problems, pages 144191. P. W. S.
Publishing Co., 1996.
 D. Bienstock, M. X. Goemans, D. SimchiLevi, and D. Williamson. A note on the prizecollecting traveling salesman
problem. Mathematical Programming, 59:413420, 1993.
