Document Open Access Logo

An Exact Algorithm for the Steiner Forest Problem

Authors Daniel R. Schmidt , Bernd Zey, François Margot

PDF

File

Thumbnail PDF
PDF
LIPIcs.ESA.2018.70.pdf
  • Filesize: 0.58 MB
  • 14 pages

Document Identifiers

Related Versions

Subject Classification

ACM Subject Classification
  • Mathematics of computing → Combinatorial optimization
Keywords
  • branch-and-bound algorithms
  • Steiner network problems

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

Abstract

The Steiner forest problem asks for a minimum weight forest that spans a given number of terminal sets. The problem has famous linear programming based 2-approximations [Agrawal et al., 1995; Goemans and Williamson, 1995; Jain, 2001] whose bottleneck is the fact that the most natural formulation of the problem as an integer linear program (ILP) has an integrality gap of 2. We propose new cut-based ILP formulations for the problem along with exact branch-and-bound based algorithms. While our new formulations cannot improve the integrality gap, we can prove that one of them yields stronger linear programming bounds than the two previous strongest formulations: The directed cut formulation [Balakrishnan et al., 1989; Chopra and Rao, 1994] and the advanced flow-based formulation by Magnanti and Raghavan [Magnanti and Raghavan, 2005]. In an experimental evaluation, we show that the linear programming bounds of the new formulations are indeed strong on practical instances and that our new branch-and-bound algorithms outperform branch-and-bound algorithms based on the previous formulations. Our formulations can be seen as a cut-based analogon to [Magnanti and Raghavan, 2005], whose existence was an open problem.

Cite As Get BibTex

Daniel R. Schmidt, Bernd Zey, and François Margot. An Exact Algorithm for the Steiner Forest Problem. In 26th Annual European Symposium on Algorithms (ESA 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 112, pp. 70:1-70:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018) https://doi.org/10.4230/LIPIcs.ESA.2018.70

Author Details

Daniel R. Schmidt
  • Institut für Informatik, Universität zu Köln, Germany
Bernd Zey
  • Fakultät für Informatik, TU Dortmund, Germany
François Margot
  • Carnegie-Mellon-University, Pittsburgh PA, USA

Funding

  • Schmidt, Daniel R.: Supported by a fellowship in the Postdoc-Program of the German Academic Exchange Service (DAAD).

References

  1. A. Agrawal, P. Klein, and R. Ravi. When trees collide: An approximation algorithm for the generalized Steiner problem on networks. SIAM Journal on Computing, 24(3):440-456, 1995. Google Scholar
  2. A. Balakrishnan, T. L. Magnanti, and R. T. Wong. A dual-ascent procedure for large-scale uncapacitated network design. Operations Research, 37(5):716-740, 1989. Google Scholar
  3. M. Bateni, M. T. Hajiaghayi, and D. Marx. Approximation schemes for Steiner forest on planar graphs and graphs of bounded treewidth. Journal of the ACM, 58(5):21:1-21:37, 2011. Google Scholar
  4. A. Björklund, T. Husfeldt, P. Kaski, and M. Koivisto. Fourier meets Möbius: Fast subset convolution. In Proceedings of the Thirty-Ninth Annual ACM Symposium on Theory of Computing, STOC '07, pages 67-74. ACM, 2007. Google Scholar
  5. B. V. Cherkassky and A. V. Goldberg. On implementing the push-relabel method for the maximum flow problem. Algorithmica, 19(4):390-410, 1997. Google Scholar
  6. S. Chopra, E. R. Gorres, and M. R. Rao. Solving the Steiner tree problem on a graph using branch and cut. ORSA Journal on Computing, 4(3):320-335, 1992. Google Scholar
  7. S. Chopra and M. R. Rao. The Steiner tree problem I: Formulations, compositions and extension of facets. Mathematical Programming, 64(1):209-229, 1994. Google Scholar
  8. S. Chopra and M. R. Rao. The Steiner tree problem II: Properties and classes of facets. Mathematical Programming, 64(1-3):231-246, 1994. Google Scholar
  9. S. E. Dreyfus and R. A. Wagner. The Steiner problem in graphs. Networks, 1(3):195-207, 1971. Google Scholar
  10. C. W. Duin and A. Volgenant. Reduction tests for the steiner problem in grapsh. Networks, 19(5):549-567, 2006. Google Scholar
  11. J. Edmonds. Submodular functions, matroids, and certain polyhedra. In M. Jünger, G. Reinelt, and G. Rinaldi, editors, Combinatorial Optimization emdash Eureka, You Shrink!, number 2570 in LNCS, pages 11-26. Springer Berlin Heidelberg, 2003. Google Scholar
  12. R. E. Erickson, C. L. Monma, and A. F. Veinott. Send-and-split method for minimum-concave-cost network flows. Mathematics of Operations Research, 12(4):634-664, 1987. Google Scholar
  13. M. X. Goemans. The Steiner tree polytope and related polyhedra. Mathematical Programming, 63(1-3):157-182, 1994. Google Scholar
  14. M. X. Goemans and Y.-S. Myung. A catalog of Steiner tree formulations. Networks, 23(1):19-28, 1993. Google Scholar
  15. M. X. Goemans and D. Williamson. A general approximation technique for constrained forest problems. SIAM Journal on Computing, 24(2):296-317, 1995. Google Scholar
  16. A. V. Goldberg and R. E. Tarjan. A new approach to the maximum-flow problem. Journal of the ACM, 35(4):921-940, 1988. Google Scholar
  17. M. Groß, A. Gupta, A. Kumar, J. Matuschke, D. R. Schmidt, M. Schmidt, and J. Verschae. A local-search algorithm for Steiner forest. In A. R. Karlin, editor, 9th Innovations in Theoretical Computer Science Conference (ITCS 2018), volume 94 of Leibniz International Proceedings in Informatics (LIPIcs), pages 31:1-31:17. Schloss DagstuhlendashLeibniz-Zentrum fuer Informatik, 2018. Google Scholar
  18. A. Gupta and A. Kumar. Greedy Algorithms for Steiner Forest. In Proceedings of the Forty-Seventh Annual ACM on Symposium on Theory of Computing, STOC '15, pages 871-878. ACM, 2015. Google Scholar
  19. S. Hougardy, J. Silvanus, and J. Vygen. Dijkstra meets Steiner: A fast exact goal-oriented Steiner tree algorithm. Mathematical Programming Computation, 9(2):135-202, 2017. Google Scholar
  20. K. Jain. A factor 2 approximation algorithm for the generalized Steiner network problem. Combinatorica, 21(1):39-60, 2001. Google Scholar
  21. D. S. Johnson, M. Minkoff, and S. Phillips. The prize collecting Steiner tree problem: Theory and practice. In Proceedings of the Symposium on Discrete Algorithms, SODA '00, pages 760-769. SIAM, 2000. Google Scholar
  22. T. Koch and A. Martin. Solving Steiner tree problems in graphs to optimality. Networks, 32(3):207-232, 1998. Google Scholar
  23. J. Könemann, S. Leonardi, G. Schäfer, and S. van Zwam. A group-strategyproof cost sharing mechanism for the Steiner forest game. SIAM Journal on Computing, 37(5):1319-1341, 2008. Google Scholar
  24. A. Lucena. Tight bounds for the Steiner problem in graphs. Technical report, RC for Process Systems Engineering, Imperial College, London, 1993. Google Scholar
  25. T. L. Magnanti and S. Raghavan. Strong formulations for network design problems with connectivity requirements. Networks, 45:61-79, 2005. Google Scholar
  26. F. Margot, A. Prodon, and T. M. Liebling. Tree polytope on 2-trees. Mathematical Programming, 63(1-3):183-191, 1994. Google Scholar
  27. T. Polzin. Algorithms for the Steiner Problem in networks. PhD thesis, Universität des Saarlandes, 2004. URL: http://scidok.sulb.uni-saarland.de/volltexte/2004/218/index.html.
  28. T. Polzin and V. S. Daneshmand. A comparison of Steiner tree relaxations. Discrete Applied Mathematics, 112(1):241-261, 2001. Google Scholar
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2025 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact
OSZAR »