Skip to main content
SpringerLink
Log in

Modeling hop-constrained and diameter-constrained minimum spanning tree problems as Steiner tree problems over layered graphs

  • Full Length Paper
  • Series A
  • Published:
Mathematical Programming Submit manuscript

Abstract

The hop-constrained minimum spanning tree problem (HMSTP) is an NP-hard problem arising in the design of centralized telecommunication networks with quality of service constraints. We show that the HMSTP is equivalent to a Steiner tree problem (STP) in an appropriate layered graph. We prove that the directed cut model for the STP defined in the layered graph, dominates the best previously known models for the HMSTP. We also show that the Steiner directed cuts in the extended layered graph space can be viewed as being a stronger version of some previously known HMSTP cuts in the original design space. Moreover, we show that these strengthened cuts can be combined and projected into new families of cuts, including facet defining ones, in the original design space. We also adapt the proposed approach to the diameter-constrained minimum spanning tree problem (DMSTP). Computational results with a branch-and-cut algorithm show that the proposed method is significantly better than previously known methods on both problems.

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

Similar content being viewed by others

References

  1. Achuthan N.R., Caccetta L., Caccetta P.A., Geelen J.F.: Computational methods for the diameter restricted minimum weight spanning tree problem. Australas. J. Comb. 10, 51–71 (1994)

    MathSciNet  MATH  Google Scholar 

  2. Chopra S., Rao M.R.: The Steiner tree problem I: formulations, compositions and extension of facets. Math. Program. 64(2), 209–229 (1994)

    Article  MathSciNet  MATH  Google Scholar 

  3. Dahl G.: The 2-hop spanning tree problem. Oper. Res. Lett. 23, 21–26 (1998)

    Article  MathSciNet  MATH  Google Scholar 

  4. Dahl G.: Notes on polyhedra associated with hop-constrained paths. Oper. Res. Lett. 25, 97–100 (1999)

    Article  MathSciNet  MATH  Google Scholar 

  5. Dahl, G., Flatberg, T., Foldnes, N., Gouveia, L.: The jump formulation for the hop-constrained minimum spanning tree problem. Tech. Rep. CIO 5, University of Lisbon (2004)

  6. Dahl G., Gouveia L., Requejo C.: On formulations and methods for the hop-constrained minimum spanning tree problem. In: Pardalos, P., Resende, M. (eds) Handbook of Optimization in Telecommunications., pp. 493–515. Springer, Berlin (2006)

    Chapter  Google Scholar 

  7. Garey M.R., Johnson D.S.: Computers and Intractability: A Guide to the Theory of NP-Completeness. W. H. Freeman, New York (1979)

    MATH  Google Scholar 

  8. Gouveia L.: Using the Miller–Tucker–Zemlin constraints to formulate a minimal spanning tree problem with hop constraints. Comput. Oper. Res. 22(9), 959–970 (1995)

    Article  MATH  Google Scholar 

  9. Gouveia L.: Multicommodity flow models for spanning trees with hop constraints. Eur. J. Oper. Res. 95(1), 178–190 (1996)

    Article  MATH  Google Scholar 

  10. Gouveia L.: Using variable redefinition for computing lower bounds for minimum spanning and Steiner trees with hop constraints. INFORMS J. Comput. 10(2), 180–188 (1998)

    Article  MathSciNet  MATH  Google Scholar 

  11. Gouveia L., Magnanti T.L.: Network flow models for designing diameter-constrained minimum- spanning and Steiner trees. Networks 41(3), 159–173 (2003)

    Article  MathSciNet  MATH  Google Scholar 

  12. Gouveia L., Magnanti T.L., Requejo C.: A 2-path approach for odd-diameter-constrained minimum spanning and Steiner trees. Networks 44(4), 254–265 (2004)

    Article  MathSciNet  MATH  Google Scholar 

  13. Gouveia L., Magnanti T.L., Requejo C.: An intersecting tree model for odd-diameter-constrained minimum spanning and Steiner trees. Ann. Oper. Res. 146, 19–39 (2006)

    Article  MathSciNet  MATH  Google Scholar 

  14. Gouveia L., Requejo C.: A new Lagrangian relaxation approach for the hop-constrained minimum spanning tree problem. Eur. J. Oper. Res. 132(3), 539–552 (2001)

    Article  MathSciNet  MATH  Google Scholar 

  15. Gouveia, L., Simonetti, L., Uchoa, E.: Modelling hop-constrained and diameter-constrained minimum spanning tree problems as Steiner tree problems over layered graphs. Tech. Rep. RPEP, vol. 8, no.7, Universidade Federal Fluminense, Engenharia de Produção, Niterói, Brazil (2008)

  16. Gruber, M., Raidl, G.R.: A new 0-1 ILP approach for the bounded diameter minimum spanning tree problem. In: Proceedings of the 2nd International Network Optimization Conference, Lisbon, pp. 178–185 (2005)

  17. Hwang F., Richards D., Winter P.: The Steiner Tree Problems. Annals of Discrete Mathematics. North-Holland, Amsterdam (1992)

    Google Scholar 

  18. Kerivin H., Mahjoub A.R.: Design of survivable networks: a survey. Networks 46(1), 1–21 (2005)

    Article  MathSciNet  MATH  Google Scholar 

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

    Article  MathSciNet  Google Scholar 

  20. Maculan N.: The Steiner problem in graphs. Ann. Discret. Math. 31, 185–212 (1987)

    MathSciNet  Google Scholar 

  21. Magnanti T.L., Wolsey L.A.: Optimal trees. In: ~Ball, M. , Magnanti, T.L. , Monma, C., Nemhauser, G. (eds) Network Models, Handbook in Operations Research and Management Science, vol. 7, pp. 503–615. Elsevier, Amsterdam (1995)

    Google Scholar 

  22. Manyem, P., Stallmann, M.F.M.: Some approximation results in multicasting. Tech. Rep. TR-96-03, North Carolina State University (1996)

  23. Noronha, T.F., Santos, A.C., Ribeiro, C.C.: Constraint programming for the diameter constrained minimum spanning tree problem. In: Proceedings of IV Latin-American Algorithms, Graphs and Optimization Symposium, Electronic Notes in Discrete Mathematics, vol. 30, pp. 93–98. Puerto Varas, Chile (2008)

  24. Oliveira, C., Pardalos, P., Resende, M.: Optimization problems in multicast tree construction. In: Handbook of Optimization in Telecommunications, pp. 701–731. Springer, Berlin (2006)

  25. Poggide Aragão M., Uchoa E., Werneck R.: Dual heuristics on the exact solution of large Steiner problems. Electron. Notes Discret. Math. 7, 150–153 (2001)

    Article  Google Scholar 

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

    Article  MathSciNet  Google Scholar 

  27. Santos, A.C., Lucena, A., Ribeiro, C.C.: Solving diameter constrained minimum spanning tree problems in dense graphs. In: Experimental and Efficient Algorithms, Lecture Notes in Computer Science, vol. 3059/2004, pp. 458–467. Springer, Berlin (2004)

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

    MathSciNet  MATH  Google Scholar 

  29. Uchoa, E.: Algoritmos para problemas de Steiner com aplicações em projeto de circuitos VLSI. Ph.D. thesis, Pontifícia Universidade Católica do Rio de Janeiro (2001)

  30. Uchoa E., Fukasawa R., Lysgaard J., Pessoa A., Poggide Aragão M., Andrade D.: Robust branch-cut-and-price for the capacitated minimum spanning tree problem over a large extended formulation. Math. Program. 112(2), 443–472 (2008)

    Article  MathSciNet  MATH  Google Scholar 

  31. Werneck, R.: Problema de Steiner em grafos: algoritmos primais, duais e exatos. Master’s thesis, Pontifícia Universidade Católica do Rio de Janeiro (2001)

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

    Article  MATH  Google Scholar 

  33. Woolston K.A., Albin S.L.: The design of centralized networks with reliability and availability constraints. Comput. Oper. Res. 15(3), 207–217 (1988)

    Article  Google Scholar 

Download references

Author information

Authors and Affiliations

  1. Faculdade de Ciências da Universidade de Lisboa, DEIO, CIO Bloco C/2, Campo Grande, 1749-016, Lisbon, Portugal

    Luis Gouveia

  2. Universidade Federal do Rio de Janeiro, PESC/COPPE, Bl. H, sala 319, Rio de Janeiro, 21941-972, Brazil

    Luidi Simonetti

  3. Departamento de Engenharia de Produção, Universidade Federal Fluminense, R. Passo da Pátria, 156, Bl.E sala 440, Niterói, 24210-240, Brazil

    Eduardo Uchoa

Authors
  1. Luis Gouveia
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Luidi Simonetti
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. Eduardo Uchoa
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Luis Gouveia.

Rights and permissions

Reprints and permissions

About this article

Cite this article

Gouveia, L., Simonetti, L. & Uchoa, E. Modeling hop-constrained and diameter-constrained minimum spanning tree problems as Steiner tree problems over layered graphs. Math. Program. 128, 123–148 (2011). https://doi.org/10.1007/s10107-009-0297-2

Download citation

  • Received:

  • Accepted:

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s10107-009-0297-2

Keywords

Mathematics Subject Classification (2000)

Search

Navigation