Skip to main content
SpringerLink
Log in

A robust and scalable algorithm for the Steiner problem in graphs

  • Full Length Paper
  • Published:
Mathematical Programming Computation Aims and scope Submit manuscript

Abstract

We present an effective heuristic for the Steiner Problem in Graphs. Its main elements are a multistart algorithm coupled with aggressive combination of elite solutions, both leveraging recently-proposed fast local searches. We also propose a fast implementation of a well-known dual ascent algorithm that not only makes our heuristics more robust (by dealing with easier cases quickly), but can also be used as a building block of an exact branch-and-bound algorithm that is quite effective for some inputs. On all graph classes we consider, our heuristic is competitive with (and sometimes more effective than) any previous approach with similar running times. It is also scalable: with long runs, we could improve or match the best published results for most open instances in the literature.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Price excludes VAT (USA)
Tax calculation will be finalised during checkout.

Instant access to the full article PDF.

Institutional subscriptions

Fig. 1
Fig. 2
Fig. 3
Fig. 4

Similar content being viewed by others

Notes

  1. Uchoa and Werneck [52] state in passing that key-vertex removal dominates Steiner vertex removal, but this is not strictly true. Some local optima for key-vertex removal can be improved by Steiner vertex removal by transforming a degree-two vertex (on a key-path) into a key vertex. We found such cases to be extremely rare in practice, however.

  2. We know from http://www.cpubenchmark.net/singleThread.html that our machine is 3.111 times faster than an 1.53 GHz AMD Athlon XP 1800+, which is 1.967 times faster (based on Tables 5.3 and A.6 from [40]) than the 900 MHz SPARC III+ Sunfire 15,000 used in their main experiments.

  3. The code from Ribeiro et al. [45] cannot handle instances G106ac and I064ac because they have a small number (454 and 6, respectively) of zero-length edges; we reset these edge lengths to 1 for this experiment, creating instances G106ac1 and I064ac1. This may increase the solution value by a negligible amount (no more than 0.001%).

  4. Detailed competition results can be found at http://dimacs11.zib.de/contest/results/results.html.

References

  1. Achterberg, T.: SCIP: solving constraint integer programs. Math. Program. Comput. 1(1), 1–41 (2009)

    Article  MathSciNet  MATH  Google Scholar 

  2. Althaus, E., Blumenstock, M.: Algorithms for the maximum weight connected subgraph and prize-collecting Steiner tree problems. In: Manuscript Presented at the 11th DIMACS/ICERM Implementation Challenge (2014)

  3. Bastos, M.P., Ribeiro, C.C.: Reactive tabu search with path-relinking for the Steiner problem in graphs. In: Ribeiro, C.C., Hansen, P. (eds.) Essays and Surveys in Metaheuristics, pp. 39–58. Kluwer, Alphen aan den Rijn (2001)

    Google Scholar 

  4. Beasley, J.: OR-Library: distributing test problems by electronic mail. J. Oper. Res. Soc. 41, 1069–1072 (1990). http://mscmga.ms.ic.ac.uk/info.html

  5. Berthold, T.: Measuring the impact of primal heuristics. Oper. Res. Lett. 41(6), 611–614 (2013)

    Article  MathSciNet  MATH  Google Scholar 

  6. Biazzo, I., Braunstein, A., Zecchina, R.: Performance of a cavity-method-based algorithm for the prize-collecting Steiner tree problem on graphs. Phys. Rev. E 86 (2012). http://arxiv.org/abs/1309.0346

  7. Biazzo, I., Muntoni, A., Braunstein, A., Zecchina, R.: On the performance of a cavity method based algorithm for the prize-collecting Steiner tree problem on graphs. In: Presentation at the 11th DIMACS/ICERM Implementation Challenge (2014)

  8. Byrka, J., Grandoni, F., Rothvoß, T., Sanità, L.: Steiner tree approximation via iterative randomized rounding. J. ACM 60(1), 6:1–6:33 (2013)

    Article  MathSciNet  MATH  Google Scholar 

  9. Cheng, X., Du, D.Z.: Steiner Trees in Industry. Springer, Berlin (2002)

    Book  MATH  Google Scholar 

  10. Chlebík, M., Chlebíková, J.: Approximation hardness of the Steiner tree problem on graphs. In: Proceedings of 8th Scandinavian Workshop on Algorithm Theory (SWAT), LNCS, vol. 2368, pp. 95–99. Springer (2002)

  11. Chopra, S., Gorres, E.R., Rao, M.R.: Solving the Steiner tree problem on a graph using branch and cut. ORSA J. Comput. 4, 320–335 (1992)

    Article  MATH  Google Scholar 

  12. Daneshmand, S.V.: Algorithmic approaches to the Steiner problem in networks. Ph.D. thesis, Universität Mannheim. http://d-nb.info/970511787/34 (2003)

  13. Dijkstra, E.W.: A note on two problems in connexion with graphs. Numer. Math. 1, 269–271 (1959)

    Article  MathSciNet  MATH  Google Scholar 

  14. Dowsland, K.: Hill-climbing, simulated annealing and the Steiner problem in graphs. Eng. Optim. 17, 91–107 (1991)

    Article  Google Scholar 

  15. Duin, C.: Steiner’s problem in graphs: approximation, reduction, variation. Ph.D. thesis, Institute for Actuarial Science and Economics, University of Amsterdam (1993)

  16. Duin, C., Volgenant, A.: Reduction tests for the Steiner problem in graphs. Networks 19, 549–567 (1989)

    Article  MathSciNet  MATH  Google Scholar 

  17. Duin, C., Voß, S.: Efficient path and vertex exchange in Steiner tree algorithms. Networks 29, 89–105 (1997)

    Article  MathSciNet  MATH  Google Scholar 

  18. Duin, C., Voß, S.: The Pilot method: a strategy for heuristic repetition with application to the Steiner problem in graphs. Networks 34, 181–191 (1999)

    Article  MathSciNet  MATH  Google Scholar 

  19. Fischetti, M., Leitner, M., Ljubic, I., Luipersbeck, M., Monaci, M., Resch, M., Salvagnin, D., Sinnl, M.: Thinning out Steiner trees: a node-based model for uniform edge costs. In: Manuscript Presented at the 11th DIMACS/ICERM Implementation Challenge (2014)

  20. Fischetti, M., Leitner, M., Ljubić, I., Luipersbeck, M., Monaci, M., Resch, M., Salvagnin, D., Sinnl, M.: Thinning out Steiner trees: a node-based model for uniform edge costs. Math. Program. Comput. 9(2), 203–229 (2017)

    Article  MathSciNet  MATH  Google Scholar 

  21. Frey, C.: Heuristiken und genetisch algorithmen für modifizierte Steinerbaumprobleme. Ph.D. thesis (1997)

  22. Gamrath, G., Koch, T., Maher, S.J., Rehfeldt, D., Shinano, Y.: SCIP-Jack: a solver for STP and variants with parallelization extensions. In: Manuscript Presented at the 11th DIMACS/ICERM Implementation Challenge (2014)

  23. Gamrath, G., Koch, T., Maher, S.J., Rehfeldt, D., Shinano, Y.: SCIP-Jack–a solver for STP and variants with parallelization extensions. Math. Program. Comput. 9(2), 231–296 (2017)

  24. Goemans, M.X., Olver, N., Rothvoß, T., Zenklusen, R.: Matroids and integrality gaps for hypergraphic Steiner tree relaxations. In: ACM Symposium on Theory of Computing (STOC), pp. 1161–1176. ACM (2012)

  25. Hougardy, S., Silvanus, J., Vygen, J.: Dijkstra meets Steiner: A fast exact goal-oriented Steiner tree algorithm. Technical Report abs/1406.0492, CoRR (2014)

  26. Hougardy, S., Silvanus, J., Vygen, J.: Dijkstra meets Steiner: a fast exact goal-oriented Steiner tree algorithm. Math. Program. Comput. 9(2), 135–202 (2017)

    Article  MathSciNet  MATH  Google Scholar 

  27. Huang, T., Young, E.F.Y.: ObSteiner: an exact algorithm for the construction of rectilinear Steiner minimum trees in the presence of complex rectilinear obstacles. IEEE Trans. Comput. Aided Des. Integr. Circuits Syst. 882–893

  28. Johnson, D.S., Koch, T., Werneck, R.F., Zachariasen, M.: 11th DIMACS Implementation Challenge in Collaboration with ICERM: Steiner Tree Problems. http://dimacs11.zib.de

  29. Juhl, D., Warme, D.M., Winter, P., Zachariasen, M.: The GeoSteiner software package for computing Steiner trees in the plane: an updated computational study. In: Manuscript Presented at the 11th DIMACS/ICERM Implementation Challenge (2014)

  30. Karp, R.: Reducibility among combinatorial problems. In: Miller, R., Thatcher, J. (eds.) Complexity of Computer Computations, pp. 85–103. Plenum, New York (1972)

    Chapter  Google Scholar 

  31. Koch, T., Martin, A.: Solving Steiner tree problems in graphs to optimality. Networks 32, 207–232 (1998)

    Article  MathSciNet  MATH  Google Scholar 

  32. Koch, T., Martin, A., Voß, S.: SteinLib: an updated library on Steiner tree problems in graphs. Tech. Rep. ZIB-Report 00-37, Konrad-Zuse-Zentrum für Informationstechnik Berlin. http://elib.zib.de/steinlib (2000)

  33. Leitner, M., Ljubic, I., Luipersbeck, M., Prossegger, M., Resch, M.: New real-world instances for the Steiner tree problem in graphs. Tech. rep., ISOR, Uni Wien. http://homepage.univie.ac.at/ivana.ljubic/research/STP/realworld-stp-report-short.pdf (2014)

  34. Mehlhorn, K.: A faster approximation algorithm for the Steiner problem in graphs. Inf. Process. Lett. 27, 125–128 (1988)

    Article  MathSciNet  MATH  Google Scholar 

  35. Minoux, M.: Efficient greedy heuristics for Steiner tree problems using reoptimization and supermodularity. INFOR 28, 221–233 (1990)

    MATH  Google Scholar 

  36. Osborne, L., Gillett, B.: A comparison of two simulated annealing algorithms applied to the directed Steiner problem on networks. ORSA J. Comp. 3(3), 213–225 (1991)

    Article  MATH  Google Scholar 

  37. Poggi de Aragão, M., Ribeiro, C.C., Uchoa, E., Werneck, R.F.: Hybrid local search for the Steiner problem in graphs. In: Ext. Abstracts of the 4th Metaheuristics International Conference, pp. 429–433. Porto (2001)

  38. Poggi de Aragão, M., Uchoa, E., Werneck, R.F.: Dual heuristics on the exact solution of large Steiner problems. In: Proceedings of Brazilian Symposium on Graphs, Algorithms and Combinatorics (GRACO), Elec. Notes in Disc. Math. vol. 7 (2001)

  39. Poggi de Aragão, M., Werneck, R.F.: On the implementation of MST-based heuristics for the Steiner problem in graphs. In: Mount, D.M., Stein, C., (eds.) Proceedings of 4th Workshop on Algorithm Engineering and Experiments (ALENEX), LNCS, vol. 2409, pp. 1–15. Springer (2002)

  40. Polzin, T.: Algorithms for the Steiner problem in networks. Ph.D. thesis, Universität des Saarlandes (2003)

  41. Polzin, T., Vahdati Daneshmand, S.: Improved algorithms for the Steiner problem in networks. Discrete Appl. Math. 112(1–3), 263–300 (2001)

    Article  MathSciNet  MATH  Google Scholar 

  42. Polzin, T., Vahdati Daneshmand, S.: The Steiner tree challenge: an updated study. In: Manuscript Contributed to the 11th DIMACS/ICERM Implementation Challenge. http://dimacs11.zib.de/downloads.html (2014)

  43. Resende, M.G.C., Werneck, R.F.: A hybrid heuristic for the \(p\)-median problem. J. Heuristics 10(1), 59–88 (2004)

    Article  MATH  Google Scholar 

  44. Ribeiro, C.C., Souza, M.C.: Tabu search for the Steiner problem in graphs. Networks 36, 138–146 (2000)

    Article  MathSciNet  MATH  Google Scholar 

  45. Ribeiro, C.C., Uchoa, E., Werneck, R.F.: A hybrid GRASP with perturbations for the Steiner problem in graphs. Informs J. Comput. 14(3), 228–246 (2002)

    Article  MathSciNet  MATH  Google Scholar 

  46. Robins, G., Zelikovsky, A.: Tighter bounds for graph Steiner tree approximation. SIAM J. Discrete Math. 19(1), 122–134 (2005)

    Article  MathSciNet  MATH  Google Scholar 

  47. Rosseti, I., Poggi de Aragão, M., Ribeiro, C.C., Uchoa, E., Werneck, R.F.: New benchmark instances for the Steiner problem in graphs. In: Ext. Abstracts of the 4th Metaheuristics International Conference, pp. 557–591. Porto (2001)

  48. Spira, P.M., Pan, A.: On finding and updating spanning trees and shortest paths. SIAM J. Comput. 4(3), 375–380 (1975)

    Article  MathSciNet  MATH  Google Scholar 

  49. Takahashi, H., Matsuyama, A.: An approximate solution for the Steiner problem in graphs. Math. Japonica 24, 573–577 (1980)

    MathSciNet  MATH  Google Scholar 

  50. Tarjan, R.E.: Data Structures and Network Algorithms. SIAM, Philadelphia (1983)

    Book  MATH  Google Scholar 

  51. Uchoa, E., Poggi de Aragão, M., Ribeiro, C.C.: Preprocessing Steiner problems from VLSI layout. Networks 40(1), 38–50 (2002)

    Article  MathSciNet  MATH  Google Scholar 

  52. Uchoa, E., Werneck, R.F.: Fast local search for the Steiner problem in graphs. ACM J. Exper. Algorithms 17(2), 2.2:1–2.2:22 (2012)

    MathSciNet  MATH  Google Scholar 

  53. Verhoeven, M.G.A., Severens, M.E.M., Aarts, E.H.L.: Local search for Steiner trees in graphs. In: Rayward-Smith, V.J., Osman, I.H., Reeves, C.R. (eds.) Modern Heuristic Search Methods. Wiley, New York (1996)

    Google Scholar 

  54. Voß, S.: Steiner’s problem in graphs: heuristic methods. Discrete Appl. Math. 40(1), 45–72 (1992)

    Article  MathSciNet  MATH  Google Scholar 

  55. Warme, D., Winter, P., Zachariasen, M.: Exact algorithms for plane Steiner tree problems: a computational study. In: Du, D., Smith, J., Rubinstein, J. (eds.) Advances in Steiner Trees, Combinatorial Optimization, vol. 6. Kluwer, Alphen aan den Rijn (2000)

    Google Scholar 

  56. Werneck, R.F.: Steiner problem in graphs: primal, dual, and exact algorithms (In Portuguese). Master’s thesis, Catholic University of Rio de Janeiro (2001)

  57. Werneck, R.F., Rosseti, I., de Aragao, M.P., Ribeiro, C.C., Uchoa, E.: New benchmark instances for the Steiner problem in graphs. In: Resende, M.G.C., Souza, J. (eds.) Metaheuristics: Computer Decision-Making, pp. 601–614. Kluwer, Alphen aan den Rijn (2003)

    Google Scholar 

  58. Wong, R.: A dual ascent approach for Steiner tree problems on a directed graph. Math. Program. 28, 271–287 (1984)

    Article  MathSciNet  MATH  Google Scholar 

  59. Zachariasen, M., Rohe, A.: Rectilinear group Steiner trees and applications in VLSI design. Tech. Rep. 00906, Institute for Discrete Mathematics, University of Bonn (2000)

Download references

Acknowledgements

We thank two anonymous referees for their suggestions on how to improve this work, and all 11th DIMACS Implementation Challenge participants for their comments. We are most grateful to David S. Johnson, not only for providing essential feedback to an early version of this paper, but also (among numerous other accomplishments) for creating and nurturing the DIMACS Challenge series and championing the field of Algorithm Engineering. We dedicate this paper to his memory.

Author information

Authors and Affiliations

  1. Microsoft Research, New York City, NY, USA

    Thomas Pajor

  2. Universidade Federal Fluminense, Niterói, RJ, Brazil

    Eduardo Uchoa

  3. San Francisco, CA, USA

    Renato F. Werneck

Authors
  1. Thomas Pajor
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Eduardo Uchoa
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. Renato F. Werneck
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Renato F. Werneck.

Additional information

R. F. Werneck with work partly done at Microsoft Research Silicon Valley.

The software that was reviewed as part of this submission has been issued the Digital Object Identifier doi:10.5281/zenodo.806231.

A Appendix

A Appendix

1.1 A.1 Additional results

This section presents detailed results and data omitted from the main text due to space constraints.

Table 12 presents more detailed information about each of the series tested in this work. Tables 13 and 14 have results for our basic MS algorithms aggregated by series. Tables 15 and 16 are similar, but refer to the GMS algorithm.

Table 12 Instance sizes
Full size table

Table 17 reports the best solution found considering all 13 runs (5 for MS, 5 for MS2, and 3 for MSK) used to build Table 7. It includes the sizes of all instances tested in this experiment. Tables 18 and 19 report results for individual MS2 runs separately, for a more detailed view. Table 20 shows detailed results for our pure branch-and-bound algorithm on some hard instances. These runs do not use reduction-based preprocessing, which is generally ineffective for these instances (Table 21).

Table 13 Multistart algorithm: average percent error relative to best known solution
Full size table
Table 14 Multistart algorithm: average running times in seconds
Full size table
Table 15 Guarded Multistart algorithm: average percent error relative to best known solution
Full size table
Table 16 Guarded Multistart algorithm: average CPU times in seconds (wall times are lower)
Full size table
Table 17 Best results found by long runs
Full size table
Table 18 Solutions found by MS2 (two-phase unguarded multistart algorithm) for open SteinLib instances, when varying the total number of iterations
Full size table
Table 19 Running times in seconds of MS2 (two-phase unguarded multistart algorithm) on open SteinLib instances, when varying the total number of iterations
Full size table
Table 20 Branch-and-bound results on select hard instances: dimensions, solution, branch-and-bound nodes, and running time in seconds
Full size table
Table 21 Comparison between our algorithm and the branch-and-ascent (B&A) algorithm by Poggi de Aragão et al. [38] on i320 instances
Full size table

Rights and permissions

Reprints and permissions

About this article

Check for updates. Verify currency and authenticity via CrossMark

Cite this article

Pajor, T., Uchoa, E. & Werneck, R.F. A robust and scalable algorithm for the Steiner problem in graphs. Math. Prog. Comp. 10, 69–118 (2018). https://doi.org/10.1007/s12532-017-0123-4

Download citation

  • Received:

  • Accepted:

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s12532-017-0123-4

Keywords

Mathematics Subject Classification

Search

Navigation