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

Barrakuda : A Hybrid Evolutionary Algorithm for Minimum Capacitated Dominating Set Problem

Author

Listed:
  • Pedro Pinacho-Davidson

    (Department of Computer Science, Faculty of Engineering, Universidad de Concepción, Concepción 4070409, Chile)

  • Christian Blum

    (Artificial Intelligence Research Institute (IIIA-CSIC), Campus of the UAB, 08193 Bellaterra, Spain)

Abstract

The minimum capacitated dominating set problem is an NP-hard variant of the well-known minimum dominating set problem in undirected graphs. This problem finds applications in the context of clustering and routing in wireless networks. Two algorithms are presented in this work. The first one is an extended version of construct, merge, solve and adapt, while the main contribution is a hybrid between a biased random key genetic algorithm and an exact approach which we labeled Barrakuda . Both algorithms are evaluated on a large set of benchmark instances from the literature. In addition, they are tested on a new, more challenging benchmark set of larger problem instances. In the context of the problem instances from the literature, the performance of our algorithms is very similar. Moreover, both algorithms clearly outperform the best approach from the literature. In contrast, Barrakuda is clearly the best-performing algorithm for the new, more challenging problem instances.

Suggested Citation

  • Pedro Pinacho-Davidson & Christian Blum, 2020. "Barrakuda : A Hybrid Evolutionary Algorithm for Minimum Capacitated Dominating Set Problem," Mathematics, MDPI, vol. 8(11), pages 1-26, October.
    • Handle: RePEc:gam:jmathe:v:8:y:2020:i:11:p:1858-:d:433634
    as

    Download full text from publisher

    File URL: https://www.mdpi.com/2227-7390/8/11/1858/pdf
    Download Restriction: no
    File URL: https://www.mdpi.com/2227-7390/8/11/1858/
    Download Restriction: no
    ---><---

    References listed on IDEAS

    as
    1. Shyong Shyu & Peng-Yeng Yin & Bertrand Lin, 2004. "An Ant Colony Optimization Algorithm for the Minimum Weight Vertex Cover Problem," Annals of Operations Research, Springer, vol. 131(1), pages 283-304, October.
    2. Thiago Noronha & Mauricio Resende & Celso Ribeiro, 2011. "A biased random-key genetic algorithm for routing and wavelength assignment," Journal of Global Optimization, Springer, vol. 50(3), pages 503-518, July.
    3. Fuyu Yuan & Chenxi Li & Xin Gao & Minghao Yin & Yiyuan Wang, 2019. "A Novel Hybrid Algorithm for Minimum Total Dominating Set Problem," Mathematics, MDPI, vol. 7(3), pages 1-11, February.
    4. Ruizhi Li & Shuli Hu & Peng Zhao & Yupeng Zhou & Minghao Yin, 2018. "A novel local search algorithm for the minimum capacitated dominating set," Journal of the Operational Research Society, Taylor & Francis Journals, vol. 69(6), pages 849-863, June.
    5. Marco Caserta & Stefan Voß, 2016. "A corridor method based hybrid algorithm for redundancy allocation," Journal of Heuristics, Springer, vol. 22(4), pages 405-429, August.
    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. José Alejandro Cornejo Acosta & Jesús García Díaz & Ricardo Menchaca-Méndez & Rolando Menchaca-Méndez, 2020. "Solving the Capacitated Vertex K-Center Problem through the Minimum Capacitated Dominating Set Problem," Mathematics, MDPI, vol. 8(9), pages 1-16, September.
    2. Fowler, John W. & Mönch, Lars, 2022. "A survey of scheduling with parallel batch (p-batch) processing," European Journal of Operational Research, Elsevier, vol. 298(1), pages 1-24.
    3. Jonatas B. C. Chagas & Julian Blank & Markus Wagner & Marcone J. F. Souza & Kalyanmoy Deb, 2021. "A non-dominated sorting based customized random-key genetic algorithm for the bi-objective traveling thief problem," Journal of Heuristics, Springer, vol. 27(3), pages 267-301, June.
    4. Andrade, Carlos E. & Toso, Rodrigo F. & Gonçalves, José F. & Resende, Mauricio G.C., 2021. "The Multi-Parent Biased Random-Key Genetic Algorithm with Implicit Path-Relinking and its real-world applications," European Journal of Operational Research, Elsevier, vol. 289(1), pages 17-30.
    5. Lin Chen & Jin Peng & Bo Zhang & Shengguo Li, 2017. "Uncertain programming model for uncertain minimum weight vertex covering problem," Journal of Intelligent Manufacturing, Springer, vol. 28(3), pages 625-632, March.
    6. Xiaoyu Yu & Jingyi Qian & Yajing Zhang & Min Kong, 2023. "Supply Chain Scheduling Method for the Coordination of Agile Production and Port Delivery Operation," Mathematics, MDPI, vol. 11(15), pages 1-24, July.
    7. Lihe Guan & Hong Wang, 2022. "A heuristic approximation algorithm of minimum dominating set based on rough set theory," Journal of Combinatorial Optimization, Springer, vol. 44(1), pages 752-769, August.
    8. Pessoa, Luciana S. & Andrade, Carlos E., 2018. "Heuristics for a flowshop scheduling problem with stepwise job objective function," European Journal of Operational Research, Elsevier, vol. 266(3), pages 950-962.
    9. Gonçalves, José Fernando & Resende, Mauricio G.C., 2015. "A biased random-key genetic algorithm for the unequal area facility layout problem," European Journal of Operational Research, Elsevier, vol. 246(1), pages 86-107.
    10. Zhang, Wenjie & Tu, Jianhua & Wu, Lidong, 2019. "A multi-start iterated greedy algorithm for the minimum weight vertex cover P3 problem," Applied Mathematics and Computation, Elsevier, vol. 349(C), pages 359-366.
    11. Dianne Villicaña-Cervantes & Omar J. Ibarra-Rojas, 2024. "Accessible location of mobile labs for COVID-19 testing," Health Care Management Science, Springer, vol. 27(1), pages 1-19, March.
    12. F. Stefanello & L. S. Buriol & M. J. Hirsch & P. M. Pardalos & T. Querido & M. G. C. Resende & M. Ritt, 2017. "On the minimization of traffic congestion in road networks with tolls," Annals of Operations Research, Springer, vol. 249(1), pages 119-139, February.
    13. Galrão Ramos, A. & Oliveira, José F. & Gonçalves, José F. & Lopes, Manuel P., 2016. "A container loading algorithm with static mechanical equilibrium stability constraints," Transportation Research Part B: Methodological, Elsevier, vol. 91(C), pages 565-581.
    14. Behzad Karimi & Seyed Taghi Akhavan Niaki & Seyyed Masih Miriha & Mahsa Ghare Hasanluo & Shima Javanmard, 2019. "A weighted K-means clustering approach to solve the redundancy allocation problem of systems having components with different failures," Journal of Risk and Reliability, , vol. 233(6), pages 925-942, December.
    15. Luzhi Wang & Shuli Hu & Mingyang Li & Junping Zhou, 2019. "An Exact Algorithm for Minimum Vertex Cover Problem," Mathematics, MDPI, vol. 7(7), pages 1-8, July.
    16. Perea, Federico & Yepes-Borrero, Juan C. & Menezes, Mozart B.C., 2023. "Acceptance Ordering Scheduling Problem: The impact of an order-portfolio on a make-to-order firm’s profitability," International Journal of Production Economics, Elsevier, vol. 264(C).
    17. Sam Heshmati & Jannes Verstichel & Eline Esprit & Greet Vanden Berghe, 2019. "Alternative e-commerce delivery policies," EURO Journal on Transportation and Logistics, Springer;EURO - The Association of European Operational Research Societies, vol. 8(3), pages 217-248, September.
    18. Soares, Leonardo Cabral R. & Carvalho, Marco Antonio M., 2020. "Biased random-key genetic algorithm for scheduling identical parallel machines with tooling constraints," European Journal of Operational Research, Elsevier, vol. 285(3), pages 955-964.
    19. Juan Li & Bin Xin & Panos M. Pardalos & Jie Chen, 2021. "Solving bi-objective uncertain stochastic resource allocation problems by the CVaR-based risk measure and decomposition-based multi-objective evolutionary algorithms," Annals of Operations Research, Springer, vol. 296(1), pages 639-666, January.
    20. Taoqing Zhou & Zhipeng Lü & Yang Wang & Junwen Ding & Bo Peng, 2016. "Multi-start iterated tabu search for the minimum weight vertex cover problem," Journal of Combinatorial Optimization, Springer, vol. 32(2), pages 368-384, August.

    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:8:y:2020:i:11:p:1858-:d:433634. 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.