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. Wayne Pullan, 2006. "Phased local search for the maximum clique problem," Journal of Combinatorial Optimization, Springer, vol. 12(3), pages 303-323, November.
    3. 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.
    4. 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.
    5. 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.
    6. 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.
    7. 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.
    8. 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.
    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. 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.
    3. 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.
    4. 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.
    5. 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.
    6. 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.
    7. 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.
    8. 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.
    9. Filipa D. Carvalho & Maria Teresa Almeida, 2017. "The triangle k-club problem," Journal of Combinatorial Optimization, Springer, vol. 33(3), pages 814-846, April.
    10. 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.
    11. 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).
    12. Lei Chen & Jing Lu & Jian Zhang & Kai-Rui Feng & Ming-Yue Zheng & Yu-Dong Cai, 2013. "Predicting Chemical Toxicity Effects Based on Chemical-Chemical Interactions," PLOS ONE, Public Library of Science, vol. 8(2), pages 1-9, February.
    13. Yi Zhou & Jin-Kao Hao & Adrien Goëffon, 2016. "A three-phased local search approach for the clique partitioning problem," Journal of Combinatorial Optimization, Springer, vol. 32(2), pages 469-491, August.
    14. Jaehn, Florian & Neumann, Simone, 2015. "Airplane boarding," European Journal of Operational Research, Elsevier, vol. 244(2), pages 339-359.
    15. Xu, Liang & Zhang, Chao & Xiao, Feng & Wang, Fan, 2017. "A robust approach to airport gate assignment with a solution-dependent uncertainty budget," Transportation Research Part B: Methodological, Elsevier, vol. 105(C), pages 458-478.
    16. Jovanovic, Raka & Sanfilippo, Antonio P. & Voß, Stefan, 2023. "Fixed set search applied to the clique partitioning problem," European Journal of Operational Research, Elsevier, vol. 309(1), pages 65-81.
    17. Hutter, Leonie & Jaehn, Florian & Neumann, Simone, 2019. "Influencing factors on airplane boarding times," Omega, Elsevier, vol. 87(C), pages 177-190.
    18. Yi Chu & Boxiao Liu & Shaowei Cai & Chuan Luo & Haihang You, 2020. "An efficient local search algorithm for solving maximum edge weight clique problem in large graphs," Journal of Combinatorial Optimization, Springer, vol. 39(4), pages 933-954, May.
    19. Sebastian Lamm & Peter Sanders & Christian Schulz & Darren Strash & Renato F. Werneck, 2017. "Finding near-optimal independent sets at scale," Journal of Heuristics, Springer, vol. 23(4), pages 207-229, August.
    20. Bert Dijk & Bruno F. Santos & Joao P. Pita, 2019. "The recoverable robust stand allocation problem: a GRU airport case study," OR Spectrum: Quantitative Approaches in Management, Springer;Gesellschaft für Operations Research e.V., vol. 41(3), pages 615-639, September.

    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.