IDEAS home Printed from https://ideas.repec.org/a/gam/jmathe/v12y2024i2p230-d1316787.html
   My bibliography  Save this article

The Budgeted Labeled Minimum Spanning Tree Problem

Author

Listed:
  • Raffaele Cerulli

    (Department of Mathematics, University of Salerno, 84084 Fisciano, SA, Italy)

  • Ciriaco D'Ambrosio

    (Department of Mathematics, University of Salerno, 84084 Fisciano, SA, Italy)

  • Domenico Serra

    (Department of Mathematics, University of Salerno, 84084 Fisciano, SA, Italy)

  • Carmine Sorgente

    (Department of Mathematics, University of Salerno, 84084 Fisciano, SA, Italy)

Abstract

In order to reduce complexity when designing multi-media communication networks, researchers often consider spanning tree problems defined on edge-labeled graphs. The earliest setting addressed in the literature aims to minimize the number of different media types, i.e., distinct labels, used in the network. Despite being extensively addressed, such a setting completely ignores edge costs. This led to the definition of more realistic versions, where budgets for the total cost, or the number of distinct labels allowed, were introduced. In this paper, we introduce and prove the NP-hardness of the Budgeted Labeled Minimum Spanning Tree problem, consisting in minimizing the cost of a spanning tree while satisfying specified budget constraints for each label type. This problem combines the challenges of cost efficiency and label diversity within a fixed budgetary framework, providing a more realistic and practical approach to network design. We provide three distinct mathematical programming formulations of the problem and design a Lagrangian approach to derive tighter lower bounds for the optimal solution of the problem. The performances of the proposed methods are assessed by conducting a series of computational experiments on a variety of randomly generated instances, which showed how the complexity of the problem increases as the size of the network, as well as the number of labels, increase and the budget restrictions are tightened.

Suggested Citation

  • Raffaele Cerulli & Ciriaco D'Ambrosio & Domenico Serra & Carmine Sorgente, 2024. "The Budgeted Labeled Minimum Spanning Tree Problem," Mathematics, MDPI, vol. 12(2), pages 1-22, January.
  • Handle: RePEc:gam:jmathe:v:12:y:2024:i:2:p:230-:d:1316787
    as

    Download full text from publisher

    File URL: https://www.mdpi.com/2227-7390/12/2/230/pdf
    Download Restriction: no

    File URL: https://www.mdpi.com/2227-7390/12/2/230/
    Download Restriction: no
    ---><---

    References listed on IDEAS

    as
    1. Francesco Carrabs & Raffaele Cerulli & Rosa Pentangelo & Andrea Raiconi, 2021. "Minimum spanning tree with conflicting edge pairs: a branch-and-cut approach," Annals of Operations Research, Springer, vol. 298(1), pages 65-78, March.
    2. Stefan Voßs & Andreas Fink & Cees Duin, 2005. "Looking Ahead with the Pilot Method," Annals of Operations Research, Springer, vol. 136(1), pages 285-302, April.
    3. Consoli, S. & Darby-Dowman, K. & Mladenovic, N. & Moreno Pérez, J.A., 2009. "Greedy Randomized Adaptive Search and Variable Neighbourhood Search for the minimum labelling spanning tree problem," European Journal of Operational Research, Elsevier, vol. 196(2), pages 440-449, July.
    4. Francesco Carrabs & Raffaele Cerulli & Manlio Gaudioso & Monica Gentili, 2013. "Lower and upper bounds for the spanning tree with minimum branch vertices," Computational Optimization and Applications, Springer, vol. 56(2), pages 405-438, October.
    5. Andreas M. Chwatal & Günther R. Raidl, 2011. "Solving the Minimum Label Spanning Tree Problem by Mathematical Programming Techniques," Advances in Operations Research, Hindawi, vol. 2011, pages 1-38, June.
    Full references (including those not matched with items on IDEAS)

    Most related items

    These are the items that most often cite the same works as this one and are cited by the same works as this one.
    1. Silva, Thiago Gouveia da & Queiroga, Eduardo & Ochi, Luiz Satoru & Cabral, Lucídio dos Anjos Formiga & Gueye, Serigne & Michelon, Philippe, 2019. "A hybrid metaheuristic for the minimum labeling spanning tree problem," European Journal of Operational Research, Elsevier, vol. 274(1), pages 22-34.
    2. Thiago Gouveia da Silva & Serigne Gueye & Philippe Michelon & Luiz Satoru Ochi & Lucídio dos Anjos Formiga Cabral, 2019. "A polyhedral approach to the generalized minimum labeling spanning tree problem," EURO Journal on Computational Optimization, Springer;EURO - The Association of European Operational Research Societies, vol. 7(1), pages 47-77, March.
    3. Zhaowei Miao & Feng Yang & Ke Fu & Dongsheng Xu, 2012. "Transshipment service through crossdocks with both soft and hard time windows," Annals of Operations Research, Springer, vol. 192(1), pages 21-47, January.
    4. Jorge Oyola & Halvard Arntzen & David L. Woodruff, 2017. "The stochastic vehicle routing problem, a literature review, Part II: solution methods," EURO Journal on Transportation and Logistics, Springer;EURO - The Association of European Operational Research Societies, vol. 6(4), pages 349-388, December.
    5. Carvalho, A.S. & Captivo, M.E. & Marques, I., 2020. "Integrating the ambulance dispatching and relocation problems to maximize system’s preparedness," European Journal of Operational Research, Elsevier, vol. 283(3), pages 1064-1080.
    6. Cerrone, C. & Cerulli, R. & Raiconi, A., 2014. "Relations, models and a memetic approach for three degree-dependent spanning tree problems," European Journal of Operational Research, Elsevier, vol. 232(3), pages 442-453.
    7. Marian Rainer-Harbach & Petrina Papazek & Günther Raidl & Bin Hu & Christian Kloimüllner, 2015. "PILOT, GRASP, and VNS approaches for the static balancing of bicycle sharing systems," Journal of Global Optimization, Springer, vol. 63(3), pages 597-629, November.
    8. Consoli, S. & Darby-Dowman, K. & Mladenovic, N. & Moreno Pérez, J.A., 2009. "Greedy Randomized Adaptive Search and Variable Neighbourhood Search for the minimum labelling spanning tree problem," European Journal of Operational Research, Elsevier, vol. 196(2), pages 440-449, July.
    9. Rafael A. Melo & Phillippe Samer & Sebastián Urrutia, 2016. "An effective decomposition approach and heuristics to generate spanning trees with a small number of branch vertices," Computational Optimization and Applications, Springer, vol. 65(3), pages 821-844, December.
    10. Jorge Moreno & Yuri Frota & Simone Martins, 2018. "An exact and heuristic approach for the d-minimum branch vertices problem," Computational Optimization and Applications, Springer, vol. 71(3), pages 829-855, December.
    11. Höller, Holger & Melián, Belén & Voí, Stefan, 2008. "Applying the pilot method to improve VNS and GRASP metaheuristics for the design of SDH/WDM networks," European Journal of Operational Research, Elsevier, vol. 191(3), pages 691-704, December.
    12. GALARZA MONTENEGRO, Bryan David & SÖRENSEN, Kenneth & VANSTEENWEGEN, Pieter, 2023. "A demand-responsive feeder service with a maximum headway at mandatory stops," Working Papers 2023001, University of Antwerp, Faculty of Business and Economics.
    13. Amadeu A. Coco & Andréa Cynthia Santos & Thiago F. Noronha, 2022. "Robust min-max regret covering problems," Computational Optimization and Applications, Springer, vol. 83(1), pages 111-141, September.
    14. Goodson, Justin C. & Thomas, Barrett W. & Ohlmann, Jeffrey W., 2017. "A rollout algorithm framework for heuristic solutions to finite-horizon stochastic dynamic programs," European Journal of Operational Research, Elsevier, vol. 258(1), pages 216-229.
    15. Michele Ciavotta & Carlo Meloni & Marco Pranzo, 2016. "Speeding up a Rollout algorithm for complex parallel machine scheduling," International Journal of Production Research, Taylor & Francis Journals, vol. 54(16), pages 4993-5009, August.
    16. Raka Jovanovic & Antonio P. Sanfilippo & Stefan Voß, 2022. "Fixed set search applied to the multi-objective minimum weighted vertex cover problem," Journal of Heuristics, Springer, vol. 28(4), pages 481-508, August.
    17. Marín, Alfredo, 2015. "Exact and heuristic solutions for the Minimum Number of Branch Vertices Spanning Tree Problem," European Journal of Operational Research, Elsevier, vol. 245(3), pages 680-689.
    18. Clímaco, João C.N. & Eugénia Captivo, M. & Pascoal, Marta M.B., 2010. "On the bicriterion - minimal cost/minimal label - spanning tree problem," European Journal of Operational Research, Elsevier, vol. 204(2), pages 199-205, July.
    19. Jorge E. Mendoza & Bruno Castanier & Christelle Guéret & Andrés L. Medaglia & Nubia Velasco, 2011. "Constructive Heuristics for the Multicompartment Vehicle Routing Problem with Stochastic Demands," Transportation Science, INFORMS, vol. 45(3), pages 346-363, August.
    20. Francesco Carrabs & Raffaele Cerulli & Ciriaco D’Ambrosio & Federica Laureana, 2021. "The Generalized Minimum Branch Vertices Problem: Properties and Polyhedral Analysis," Journal of Optimization Theory and Applications, Springer, vol. 188(2), pages 356-377, February.

    Corrections

    All material on this site has been provided by the respective publishers and authors. You can help correct errors and omissions. When requesting a correction, please mention this item's handle: RePEc:gam:jmathe:v:12:y:2024:i:2:p:230-:d:1316787. See general information about how to correct material in RePEc.

    If you have authored this item and are not yet registered with RePEc, we encourage you to do it here. This allows to link your profile to this item. It also allows you to accept potential citations to this item that we are uncertain about.

    If CitEc recognized a bibliographic reference but did not link an item in RePEc to it, you can help with this form .

    If you know of missing items citing this one, you can help us creating those links by adding the relevant references in the same way as above, for each refering item. If you are a registered author of this item, you may also want to check the "citations" tab in your RePEc Author Service profile, as there may be some citations waiting for confirmation.

    For technical questions regarding this item, or to correct its authors, title, abstract, bibliographic or download information, contact: MDPI Indexing Manager (email available below). General contact details of provider: https://www.mdpi.com .

    Please note that corrections may take a couple of weeks to filter through the various RePEc services.

    IDEAS is a RePEc service. RePEc uses bibliographic data supplied by the respective publishers.