Skip to main content
SpringerLink
Log in

A hybrid heuristic for the diameter constrained minimum spanning tree problem

  • Published:
Journal of Global Optimization Aims and scope Submit manuscript

Abstract

We propose a hybrid GRASP and ILS based heuristic for the diameter constrained minimum spanning tree problem. The latter typically models network design applications where, under a given quality requirement, all vertices must be connected at minimum cost. An adaptation of the one time tree heuristic is used to build feasible diameter constrained spanning trees. Solutions thus obtained are then attempted to be improved through local search. Four different neighborhoods are investigated, in a scheme similar to VND. Upper bounds within 2% of optimality were obtained for problems in two test sets from the literature. Additionally, upper bounds stronger than those previously obtained in the literature are reported for OR-Library instances.

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. Abdalla, A.M.: Computing a diameter-constrained minimum spanning tree. PhD thesis, College of Engineering and Computing Science, University of Central Florida, Orlando (2001)

  2. Achuthan N.R., Caccetta L., Caccetta P.A., Geelen J.F.: Algorithms for the minimum weight spanning tree with bounded diameter problem. In: Phua, K.H., Wand, C.M., Yeong, W.Y., Leong, T.Y., Loh, H.T., Tan, K.C., Chou, F.S. (eds) Optimization Techniques and Applications, vol. 1, pp. 297–304. World Scientific, Singapore (1992)

    Google Scholar 

  3. 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)

    Google Scholar 

  4. Bala, K., Petropoulos, K., Stern, E.: Multicasting in a linear lightwave network. In: Proceedings of the IEEE INFOCOM’93 Conference on Computer Communications, vol. 3, pp. 31350–31358. São Francisco (1993)

  5. Beasley E.J.: OR-Library: distributing test problems by electronic mail. J. Oper. Res. Soc. 41, 1069–1072 (1990)

    Article  Google Scholar 

  6. Bookstein A., Klein S.T.: Compression of correlated bitvectors. Inf. Syst. 16, 110–118 (2001)

    Google Scholar 

  7. Deo N., Abdalla A.: Computing a diameter-constrained minimum spanning tree in parallel. Lect. Notes Comput. Sci. 1767, 17–31 (2000)

    Article  Google Scholar 

  8. Duarte, A.R., Ribeiro, C.C., Urrutia, S., Haeusler, E.H.: Referee assignment in sports leagues. In: Practice and Theory of Automated Timetabling VI, vol. 3867 of Lecture Notes in Computer Science, pp. 158–173. Springer (2007)

  9. Feo T.A., Resende M.G.C.: A probabilistic heuristic for a computationally difficult set covering problem. Oper. Res. Lett. 8, 67–71 (1989)

    Article  Google Scholar 

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

    Google Scholar 

  11. Gouveia L., Magnanti T.L.: Modelling and Solving the Diameter-Constrained Minimum Spanning Tree Problem, Technical Report. Departamento de Estatística e Investigação Operational, Faculdade de Ciências, Lisboa (2000)

    Google Scholar 

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

    Article  Google Scholar 

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

    Article  Google Scholar 

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

  15. Gruber, M., Raidl, G.R.: Variable neighborhood search for the bounded diameter minimum spanning tree problem. In: Hansen, P., Mladenovic, N., Pérez, J.A.M., Batista, B.M., MorenoVega, J.M. (eds.) (2005) Proceedings of the 18th Mini Euro Conference on Variable Neighborhood Search, pp. 1–11. Tenerife

  16. Guedes, A.C.B., Ribeiro, C.C.: A hybrid heuristic for minimizing weighted carry-over effects in round robin tournaments (2009) (Submitted)

  17. Handler G.Y.: Minimax location of a facility in an undirected graph. Transp. Sci. 7, 287–293 (1978)

    Article  Google Scholar 

  18. Hansen P., Mladenović N.: Variable neighborhood search: principles and applications. Euro. J. Oper. Res. 130, 449–467 (2001)

    Article  Google Scholar 

  19. Hansen P., Mladenović N.: Developments of variable neighborhood search. In: Ribeiro, C.C., Hansen, P. Essays and Surveys in Metaheuristics, pp. 415–439. Kluwer, Boston (2002)

  20. Hart J.P., Shogan A.W.: Semi-greedy heuristics: An empirical study. Oper. Res. Lett. 6, 107–114 (1987)

    Article  Google Scholar 

  21. Julstrom, B., Raidl, G.R.: A permutation-coded evolutionary algorithm for the bounded-diameter minimum spanning tree problem. In: Barry, A., Rothlauf, F., Thierens, D., et al. (eds.) The Genetic and Evolutionary Computation Conference’s Workshops Proceedings, Workshop on Analysis and Design of Representations, pp. 2–7. Chicago (2003)

  22. Julstrom B. A.: Encoding bounded-diameter minimum spanning trees with permutations and with random keys. Lect. Notes Comput. Sci. 3102, 1272–1281 (2004)

    Google Scholar 

  23. Lourenço, H.R., Martin, O.C., Stutzle, T.: Iterated local search. In: Glover F., KochenbergerG. Handbook of Metaheuristics, pp. 321–353. Kluwer, Boston (2002)

  24. Prais, M., Ribeiro, C.C. : Reactive GRASP: an application to a matrix decomposition problem in TDMA traffic assignment. INFORMS J. Comput. 12, 164–176 (2000)

    Article  Google Scholar 

  25. Prim R.C.: Shortest connection networks and some generalizations. Bell Syst. Tech. J. 36, 1389–1401 (1957)

    Google Scholar 

  26. Raidl, G.R., Julstrom, B.A. : Greedy heuristics and an evolutionary algorithm for the bounded-diameter minimum spanning tree problem. In: Proceedings of the 18th ACM Symposium on Applied Computing, pp. 747–752. Melbourne (USA) (2003)

  27. Raymond K.: A tree-based algorithm for distributed mutual exclusion. ACM Trans. Comput. 7, 61–77 (1989)

    Article  Google Scholar 

  28. Requejo, C.: Modelos para o problema da árvore geradora de suporte com restrição de diâmetro: caso do diâmetro ímpar. PhD thesis, Universidade de Lisboa Faculdade de Ciências, Lisboa (2003)

  29. Resende M.G.C., Ribeiro C.C.: Greedy randomized adaptive search procedures. In: Glover, F., Kochenberger, G. (eds) Handbook of Metaheuristics, pp. 219–249. Kluwer, Boston (2003)

    Google Scholar 

  30. Ribeiro C.C., Urrutia S.: Heuristics for the mirrored traveling tournament problem. Euro. J. Oper. Res. 179, 775–787 (2007)

    Article  Google Scholar 

  31. Santos A.C., Lucena A., Ribeiro C.C.: Solving diameter constrained minimum spanning tree problem in dense graphs. Lect. Notes Comput. Sci. 3059, 458–467 (2004)

    Google Scholar 

Download references

Author information

Authors and Affiliations

  1. Federal University of Rio de Janeiro, Av. Pasteur 250, Rio de Janeiro, RJ, 22290-240, Brazil

    Abilio Lucena

  2. Institute of Computing, Federal University Fluminense, Rua Passo da Pátria 156, Niterói, RJ, 24210-240, Brazil

    Celso C. Ribeiro

  3. Blaise Pascal University, LIMOS, Complexe Scientifique des Cézeaux, 63173, Aubière, France

    Andréa C. Santos

Authors
  1. Abilio Lucena
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Celso C. Ribeiro
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. Andréa C. Santos
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Celso C. Ribeiro.

Rights and permissions

Reprints and permissions

About this article

Cite this article

Lucena, A., Ribeiro, C.C. & Santos, A.C. A hybrid heuristic for the diameter constrained minimum spanning tree problem. J Glob Optim 46, 363–381 (2010). https://doi.org/10.1007/s10898-009-9430-2

Download citation

  • Received:

  • Accepted:

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s10898-009-9430-2

Keywords

Search

Navigation