IDEAS home Printed from https://ideas.repec.org/a/spr/opsear/v55y2018i2d10.1007_s12597-017-0325-6.html
   My bibliography  Save this article

A heuristic based harmony search algorithm for maximum clique problem

Author

Listed:
  • Assif Assad

    (Indian Institute of Technology Roorkee)

  • Kusum Deep

    (Indian Institute of Technology Roorkee)

Abstract

The maximum clique problem (MCP) is to determine a complete subgraph (clique) of maximum cardinality in a given graph. MCP is conspicuous for having real world applications and for its potentiality of modeling other combinatorial problems and is one of the most studied NP-hard problems. This paper investigates the capabilities of Harmony Search (HS) algorithm, a music inspired meta heuristic for solving maximum clique problem. We propose and compare two different instantiations of a generic HS algorithm namely Harmony Search for MCP (HS_MCP) and Harmony Search with idiosyncratic harmonies for MCP (HSI_MCP) for this problem. HS_MCP has better exploitation and inferior exploration capabilities than HSI_MCP whereas HSI_MCP has better exploration and inferior exploitation capabilities than HSI_MCP, it has been concluded that former performs better than latter by testing them on all the instances of DIMACS benchmark graphs. HS_MCP has been compared with a recently proposed Harmony search based algorithm for MCP called Binary Harmony search (BHS) and the simulation results show that HS_MCP significantly outperforms BHS in terms of solution quality. The asymptotic time complexity of HS_MCP is $$O(G \times N^3)$$ O ( G × N 3 ) where G is the number of generations and N is the number of nodes in the graph. A glimpse of effectiveness of some state-of-the-art exact algorithms on MCP has also been provided.

Suggested Citation

  • Assif Assad & Kusum Deep, 2018. "A heuristic based harmony search algorithm for maximum clique problem," OPSEARCH, Springer;Operational Research Society of India, vol. 55(2), pages 411-433, June.
    • Handle: RePEc:spr:opsear:v:55:y:2018:i:2:d:10.1007_s12597-017-0325-6
    DOI: 10.1007/s12597-017-0325-6
    as

    Download full text from publisher

    File URL: http://link.springer.com/10.1007/s12597-017-0325-6
    File Function: Abstract
    Download Restriction: Access to the full text of the articles in this series is restricted.
    File URL: https://libkey.io/10.1007/s12597-017-0325-6?utm_source=ideas
    LibKey link: if access is restricted and if your library uses this service, LibKey will redirect you to where you can use your library subscription to access this item
    ---><---

    As the access to this document is restricted, you may want to search for a different version of it.

    References listed on IDEAS

    as
    1. Evgeny Maslov & Mikhail Batsyn & Panos Pardalos, 2014. "Speeding up branch and bound algorithms for solving the maximum clique problem," Journal of Global Optimization, Springer, vol. 59(1), pages 1-21, May.
    2. Balabhaskar Balasundaram & Sergiy Butenko & Illya V. Hicks, 2011. "Clique Relaxations in Social Network Analysis: The Maximum k -Plex Problem," Operations Research, INFORMS, vol. 59(1), pages 133-142, February.
    3. Wayne Pullan, 2006. "Phased local search for the maximum clique problem," Journal of Combinatorial Optimization, Springer, vol. 12(3), pages 303-323, November.
    4. Mikhail Batsyn & Boris Goldengorin & Evgeny Maslov & Panos M. Pardalos, 2014. "Improvements to MCS algorithm for the maximum clique problem," Journal of Combinatorial Optimization, Springer, vol. 27(2), pages 397-416, February.
    5. Martín Gómez Ravetti & Pablo Moscato, 2008. "Identification of a 5-Protein Biomarker Molecular Signature for Predicting Alzheimer's Disease," PLOS ONE, Public Library of Science, vol. 3(9), pages 1-12, September.
    6. Jeffrey Pattillo & Nataly Youssef & Sergiy Butenko, 2012. "Clique Relaxation Models in Social Network Analysis," Springer Optimization and Its Applications, in: My T. Thai & Panos M. Pardalos (ed.), Handbook of Optimization in Complex Networks, chapter 0, pages 143-162, Springer.
    7. Ulrich Dorndorf & Florian Jaehn & Erwin Pesch, 2008. "Modelling Robust Flight-Gate Scheduling as a Clique Partitioning Problem," Transportation Science, INFORMS, vol. 42(3), pages 292-301, August.
    8. M W Carter & D G Johnson, 2001. "Extended clique initialisation in examination timetabling," Journal of the Operational Research Society, Palgrave Macmillan;The OR Society, vol. 52(5), pages 538-544, May.
    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. Mahmudul Hasan & Md. Rafiqul Islam & Amrita Ghosh Mugdha, 2023. "Solving maximum clique problem using chemical reaction optimization," OPSEARCH, Springer;Operational Research Society of India, vol. 60(3), pages 1230-1266, September.

    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. Wu, Qinghua & Hao, Jin-Kao, 2015. "A review on algorithms for maximum clique problems," European Journal of Operational Research, Elsevier, vol. 242(3), pages 693-709.
    2. Seyedmohammadhossein Hosseinian & Dalila B. M. M. Fontes & Sergiy Butenko, 2020. "A Lagrangian Bound on the Clique Number and an Exact Algorithm for the Maximum Edge Weight Clique Problem," INFORMS Journal on Computing, INFORMS, vol. 32(3), pages 747-762, July.
    3. Zhou, Yi & Lin, Weibo & Hao, Jin-Kao & Xiao, Mingyu & Jin, Yan, 2022. "An effective branch-and-bound algorithm for the maximum s-bundle problem," European Journal of Operational Research, Elsevier, vol. 297(1), pages 27-39.
    4. Stefano Coniglio & Stefano Gualandi, 2022. "Optimizing over the Closure of Rank Inequalities with a Small Right-Hand Side for the Maximum Stable Set Problem via Bilevel Programming," INFORMS Journal on Computing, INFORMS, vol. 34(2), pages 1006-1023, March.
    5. Timo Gschwind & Stefan Irnich & Fabio Furini & Roberto Wolfler Calvo, 2017. "Social Network Analysis and Community Detection by Decomposing a Graph into Relaxed Cliques," Working Papers 1722, Gutenberg School of Management and Economics, Johannes Gutenberg-Universität Mainz.
    6. Zhou, Qing & Benlic, Una & Wu, Qinghua, 2020. "An opposition-based memetic algorithm for the maximum quasi-clique problem," European Journal of Operational Research, Elsevier, vol. 286(1), pages 63-83.
    7. David Bergman & Andre A. Cire & Willem-Jan van Hoeve & J. N. Hooker, 2016. "Discrete Optimization with Decision Diagrams," INFORMS Journal on Computing, INFORMS, vol. 28(1), pages 47-66, February.
    8. Zhuqi Miao & Balabhaskar Balasundaram & Eduardo L. Pasiliao, 2014. "An exact algorithm for the maximum probabilistic clique problem," Journal of Combinatorial Optimization, Springer, vol. 28(1), pages 105-120, July.
    9. Ulrich Dorndorf & Florian Jaehn & Erwin Pesch, 2017. "Flight gate assignment and recovery strategies with stochastic arrival and departure times," OR Spectrum: Quantitative Approaches in Management, Springer;Gesellschaft für Operations Research e.V., vol. 39(1), pages 65-93, January.
    10. Oleksandra Yezerska & Foad Mahdavi Pajouh & Alexander Veremyev & Sergiy Butenko, 2019. "Exact algorithms for the minimum s-club partitioning problem," Annals of Operations Research, Springer, vol. 276(1), pages 267-291, May.
    11. S. Raghavan & Rui Zhang, 2022. "Rapid Influence Maximization on Social Networks: The Positive Influence Dominating Set Problem," INFORMS Journal on Computing, INFORMS, vol. 34(3), pages 1345-1365, May.
    12. Zhiqiang Zhang & Zhongwen Li & Xiaobing Qiao & Weijun Wang, 2019. "An Efficient Memetic Algorithm for the Minimum Load Coloring Problem," Mathematics, MDPI, vol. 7(5), pages 1-20, May.
    13. Filipa D. Carvalho & Maria Teresa Almeida, 2017. "The triangle k-club problem," Journal of Combinatorial Optimization, Springer, vol. 33(3), pages 814-846, April.
    14. Zhou, Yi & Rossi, André & Hao, Jin-Kao, 2018. "Towards effective exact methods for the Maximum Balanced Biclique Problem in bipartite graphs," European Journal of Operational Research, Elsevier, vol. 269(3), pages 834-843.
    15. Foad Mahdavi Pajouh & Balabhaskar Balasundaram & Illya V. Hicks, 2016. "On the 2-Club Polytope of Graphs," Operations Research, INFORMS, vol. 64(6), pages 1466-1481, December.
    16. Larisa Komosko & Mikhail Batsyn & Pablo San Segundo & Panos M. Pardalos, 2016. "A fast greedy sequential heuristic for the vertex colouring problem based on bitwise operations," Journal of Combinatorial Optimization, Springer, vol. 31(4), pages 1665-1677, May.
    17. Zhao, Peixin & Han, Xue & Wan, Di, 2021. "Evaluation of the airport ferry vehicle scheduling based on network maximum flow model," Omega, Elsevier, vol. 99(C).
    18. Yuan Sun & Andreas Ernst & Xiaodong Li & Jake Weiner, 2021. "Generalization of machine learning for problem reduction: a case study on travelling salesman problems," OR Spectrum: Quantitative Approaches in Management, Springer;Gesellschaft für Operations Research e.V., vol. 43(3), pages 607-633, September.
    19. Sándor Szabó, 2021. "A Clique Search Problem and its Application to Machine Scheduling," SN Operations Research Forum, Springer, vol. 2(4), pages 1-12, December.
    20. Timo Gschwind & Stefan Irnich & Fabio Furini & Roberto Wolfler Calvo, 2017. "A Branch-and-Price Framework for Decomposing Graphs into Relaxed Cliques," Working Papers 1723, Gutenberg School of Management and Economics, Johannes Gutenberg-Universität Mainz.

    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:spr:opsear:v:55:y:2018:i:2:d:10.1007_s12597-017-0325-6. 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: Sonal Shukla or Springer Nature Abstracting and Indexing (email available below). General contact details of provider: http://www.springer.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.