Skip to main content
SpringerLink
Log in

Branch-and-cut-and-price algorithms for the Degree Constrained Minimum Spanning Tree Problem

  • Published:
Computational Optimization and Applications Aims and scope Submit manuscript

Abstract

Assume that a connected undirected edge weighted graph G is given. The Degree Constrained Minimum Spanning Tree Problem (DCMSTP) asks for a minimum cost spanning tree of G where vertex degrees do not exceed given pre-defined upper bounds. In this paper, three exact solution algorithms are investigated for the problem. All of them are Branch-and-cut based and rely on the strongest formulation currently available for the problem. Additionally, to speed up the computation of dual bounds, they all use column generation, in one way or another. To test the algorithms, new hard to solve DCMSTP instances are proposed here. These instances, combined with additional ones taken from the literature, are then used in computational experiments. The experiments compare the new algorithms among themselves and also against the best algorithms currently available in the literature. As an outcome of them, one of the new algorithms stands out on top.

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

Similar content being viewed by others

References

  1. Achterberg, T., Koch, T., Martin, A.: Branching rules revisited. Oper. Res. Lett. 33(1), 42–54 (2005)

    Article  MathSciNet  MATH  Google Scholar 

  2. Andrade, R.C., Freitas, A.T.: Disjunctive combinatorial branch in a subgradient tree algorithm for the DCMST problem with VNS-Lagrangian bounds. Electron. Notes Discrete Math. 41, 5–12 (2013)

    Article  Google Scholar 

  3. Andrade, R., Lucena, A., Maculan, N.: Using lagrangian dual information to generate degree constrained spanning trees. Discrete Appl. Math. 154(5), 703–717 (2006)

    Article  MathSciNet  MATH  Google Scholar 

  4. Caccetta, L., Hill, S.P.: A branch and cut method for the degree-constrained minimum spanning tree problem. Networks 37(2), 74–83 (2001)

    Article  MathSciNet  MATH  Google Scholar 

  5. Craig, G., Krishnamoorthy, M., Palaniswami, M.: Comparison of heuristic algorithms for the degree constrained minimum spanning tree. In: Osman, I.H., Kelly, J.P. (eds.) Metaheuristics: Theory and Applications, pp. 83–96. Kluwer, Boston (1996)

    Google Scholar 

  6. da Cunha, A., Lucena, A.: Lower and upper bounds for the degree-constrained minimum spanning tree problem. Networks 50(1), 55–66 (2007)

    Article  MathSciNet  MATH  Google Scholar 

  7. Dantzig, G., Fulkerson, D., Johnson, S.: Solution of a large scale traveling salesman problem. Oper. Res. 2(4), 393–410 (1954)

    MathSciNet  Google Scholar 

  8. de Souza, M., Martins, P.: Skewed VNS enclosing second order algorithm for the degree constrained minimum spanning tree problem. Eur. J. Oper. Res. 191(3), 677–690 (2008)

    Article  MATH  Google Scholar 

  9. Dolan, E.D., Moré, J.J.: Benchmark optimization software with performance profiles. Math. Program. 91(2), 201–213 (2002)

    Article  MathSciNet  MATH  Google Scholar 

  10. Fages, J., Lorca, X., Rousseau, L.: Une approche basée sur les contraintes pour résoudre le problème d’arbre recouvrant de coût minimum avec contraintes de degré. In: Actes JFPC, pp. 119–122 (2013)

  11. Fischetti, M., Lodi, A.: Local branching. Math. Program. 98(1–3), 23–47 (2003)

    Article  MathSciNet  MATH  Google Scholar 

  12. Freitas, A.: Árvore de subgradiente com pré-fase VNS-Lagrangeana para o problema da árvore geradora mínima com restrição de grau máximo nos vértices. Master’s thesis, Departamento de Computação, Universidade Federal do Ceará, Fortaleza, CE, Brasil (2011)

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

    MATH  Google Scholar 

  14. Gavish, B.: Topological design of centralized computer networks—formulations and algorithms. Networks 12(4), 355–377 (1982)

    Article  MathSciNet  MATH  Google Scholar 

  15. Geoffrion, A.: Lagrangean relaxation for integer programming. In: Balinski, M. (ed.) Mathematical Programming Studies, vol. 2, pp. 82–114. Springer, Berlin (1974)

    Google Scholar 

  16. Koch, T., Martin, A.: Solving steiner tree problems in graphs to optimality. Networks 32(3), 207–233 (1998)

    Article  MathSciNet  MATH  Google Scholar 

  17. Kruskal, J.B.: On the shortest spanning subtree of a graph and the traveling salesman problem. Proc. Am. Math. Soc. 7(1), 48–50 (1956)

    Article  MathSciNet  MATH  Google Scholar 

  18. Letchford, A.N., Reinelt, G., Theis, D.O.: A faster exact separation algorithm for blossom inequalities. In: Integer Programming and Combinatorial Optimization, pp. 196–205. Springer, Berlin (2004)

  19. Lucena, A., Resende, M.: Strong lower bounds for the prize collecting steiner problem in graphs. Discrete Appl. Math. 141(1), 277–294 (2004)

    Article  MathSciNet  MATH  Google Scholar 

  20. Lucena, A., Maculan, N., da Cunha, A.: Relax-and-cut as a preprocessor and warm starter to branch-and-cut. In: Mahjoub, A.R. (ed.) Progress in Combinatorial Optimization, Chap. 5, pp. 171–197. Wiley, New York (2011)

    Google Scholar 

  21. Narula, S., Ho, C.: Degree-constrained minimum spanning tree. Comput. Oper. Res. 7(4), 239–249 (1980)

    Article  Google Scholar 

  22. Obruča, A.K.: Spanning tree manipulation and the travelling salesman problem. Comput. J. 10(4), 374–377 (1968)

    Article  Google Scholar 

  23. Padberg, M., Wolsey, L.: Trees and cuts. N. Holl. Math. Stud. 75, 511–517 (1983)

    Article  MathSciNet  Google Scholar 

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

    Article  Google Scholar 

  25. Ribeiro, C., de Souza, M.: Variable neighborhood search for the degree-constrained minimum spanning tree problem. Discrete Appl. Math. 118(1), 43–54 (2002)

    Article  MathSciNet  MATH  Google Scholar 

  26. Volgenant, A.: A lagrangean approach to the degree-constrained minimum spanning tree problem. Eur. J. Oper. Res. 39(3), 325–331 (1989)

    Article  MathSciNet  MATH  Google Scholar 

  27. Zhou, G., Gen, M.: A note on genetic algorithms for degree-constrained spanning tree problems. Networks 30(2), 91–95 (1997)

    Article  MATH  Google Scholar 

Download references

Acknowledgments

Alexandre Salles da Cunha is partially funded by CNPq Grants 305423/2012-6, 471464/2013-9 and FAPEMIG CEX-PPM-00164-13. Abilio Lucena is partially funded by CNPq Grant 310561/2009-4 and FAPERJ Grant E26-110.552/2010.

Author information

Authors and Affiliations

  1. Departamento de Ciência da Computação, Universidade Federal de Minas Gerais, Belo Horizonte, Brazil

    Luis Henrique Bicalho & Alexandre Salles da Cunha

  2. Programa de Engenharia de Sistemas e Computação, Universidade Federal do Rio de Janeiro, Rio de Janeiro, Brazil

    Abilio Lucena

Authors
  1. Luis Henrique Bicalho
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Alexandre Salles da Cunha
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. Abilio Lucena
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Alexandre Salles da Cunha.

Rights and permissions

Reprints and permissions

About this article

Check for updates. Verify currency and authenticity via CrossMark

Cite this article

Bicalho, L.H., da Cunha, A.S. & Lucena, A. Branch-and-cut-and-price algorithms for the Degree Constrained Minimum Spanning Tree Problem. Comput Optim Appl 63, 755–792 (2016). https://doi.org/10.1007/s10589-015-9788-7

Download citation

  • Received:

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s10589-015-9788-7

Keywords

Search

Navigation