Prize-Collecting Steiner Tree Problem: A branch-and-cut algorithm (DHEA)

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.

An input graph G: hollow circles represent customers

A feasible but not optimal PCST solution

Download

dhea-code is a branch-and-cut algorithm for solving the undirected prize-collecting Steiner tree problem. Main features of the algorithm are described in:

I. Ljubić, 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.
Ivana Ljubić.
Exact and Memetic Algorithms for Two Network Design Problems.
PhD thesis, Faculty of Computer Science, Vienna University of Technology, November 2004.

Executable-File for 64-bit machines can be downloaded HERE
Executable-File for 32-bit machines (Linux/Unix-Platform) can be downloaded HERE
User Manual

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. More details are coming soon...
BIOINFORMATICS: The dhea code has been successfully used in a recent study to find functional modules in cancer interactome data. For further details see HEINZ library and a web-page of Gunnar Klau.

Licensing © 2003 - 2008

This code is free software. You can redistribute it and/or modify it under the terms of the GNU Lesser General Public License as published by the Free Software Foundation; either version 2.1 of the License, or (at your option) any later version. This code is distributed in the hope that it will be useful, but WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU Lesser General Public License for more details. The dhea-code has been developed with non-commercial LEDA/CPLEX licenses for academic purposes only. 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:

LEDA 5.1.1, owned by Algorithmic Solutions Software GmbH.
CPLEX 10.0, owned by ILOG.

Benchmark instances

Instances from Mauricio Resende's web-page:

Groups C and D: Download (4MB)
K and P groups: Download (0.3MB)

Group E: Download (5.8MB)
Real-world instances: Cologne1 (8.9MB) and Cologne2 (48.4MB)
After preprocessing described in Ljubić 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

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
E. Uchoa: Reduction tests for the prize-collecting Steiner problem. Oper. Res. Lett. 34(4): 437-444. 2006.
I. Ljubić, 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.
O. Chapovska, A. P. Punnen: Variations of the prize-collecting Steiner tree problem. Networks 47(4): 199-205. 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. Ljubić, 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.
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.
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.
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.
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.
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.
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.

Ivana LJUBIC