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. 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.
    2. 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.
    3. 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.
    4. 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.
    5. 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.
    Full references (including those not matched with items on IDEAS)

    Citations

    Citations are extracted by the CitEc Project, subscribe to its RSS feed for this item.
    as


    Cited by:

    1. Londe, Mariana A. & Pessoa, Luciana S. & Andrade, Carlos E. & Resende, Mauricio G.C., 2025. "Biased random-key genetic algorithms: A review," European Journal of Operational Research, Elsevier, vol. 321(1), pages 1-22.

    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. 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.
    5. 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.
    6. 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.
    7. 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.
    8. 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.
    9. 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.
    10. 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).
    11. 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.
    12. Luciano Ferreira Cruz & Flavia Bernardo Pinto & Lucas Camilotti & Angelo Marcio Oliveira Santanna & Roberto Zanetti Freire & Leandro Santos Coelho, 2022. "Improved multiobjective differential evolution with spherical pruning algorithm for optimizing 3D printing technology parametrization process," Annals of Operations Research, Springer, vol. 319(2), pages 1565-1587, December.
    13. Gonçalves, José Fernando & Wäscher, Gerhard, 2020. "A MIP model and a biased random-key genetic algorithm based approach for a two-dimensional cutting problem with defects," European Journal of Operational Research, Elsevier, vol. 286(3), pages 867-882.
    14. Julliany S. Brandão & Thiago F. Noronha & Celso C. Ribeiro, 2016. "A biased random-key genetic algorithm to maximize the number of accepted lightpaths in WDM optical networks," Journal of Global Optimization, Springer, vol. 65(4), pages 813-835, August.
    15. Tangpattanakul, Panwadee & Jozefowiez, Nicolas & Lopez, Pierre, 2015. "A multi-objective local search heuristic for scheduling Earth observations taken by an agile satellite," European Journal of Operational Research, Elsevier, vol. 245(2), pages 542-554.
    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. Lin, B.M.T. & Lu, C.Y. & Shyu, S.J. & Tsai, C.Y., 2008. "Development of new features of ant colony optimization for flowshop scheduling," International Journal of Production Economics, Elsevier, vol. 112(2), pages 742-755, April.
    18. Xinyun Wu & Shengfeng Yan & Xin Wan & Zhipeng Lü, 2016. "Multi-neighborhood based iterated tabu search for routing and wavelength assignment problem," Journal of Combinatorial Optimization, Springer, vol. 32(2), pages 445-468, August.
    19. Geiza Silva & André Leite & Raydonal Ospina & Víctor Leiva & Jorge Figueroa-Zúñiga & Cecilia Castro, 2023. "Biased Random-Key Genetic Algorithm with Local Search Applied to the Maximum Diversity Problem," Mathematics, MDPI, vol. 11(14), pages 1-11, July.
    20. Pinto, Bruno Q. & Ribeiro, Celso C. & Rosseti, Isabel & Plastino, Alexandre, 2018. "A biased random-key genetic algorithm for the maximum quasi-clique problem," European Journal of Operational Research, Elsevier, vol. 271(3), pages 849-865.

    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.