IDEAS home Printed from https://ideas.repec.org/a/spr/opsear/v60y2023i3d10.1007_s12597-023-00654-z.html
   My bibliography  Save this article

Solving maximum clique problem using chemical reaction optimization

Author

Listed:
  • Mahmudul Hasan

    (Khulna University)

  • Md. Rafiqul Islam

    (Khulna University)

  • Amrita Ghosh Mugdha

    (Khulna University)

Abstract

The maximum clique problem (MCP) deals with a given arbitrary graph that finds the maximum clique in the graph. The target is to maximize the size of the clique which means maximizing the size of a complete subgraph. The MCP finds the largest complete subgraph or clique of a given graph. Several metaheuristic approaches were proposed to solve the problem as it is an NP-hard problem. To solve the maximum clique problem we propose a metaheuristic algorithm named chemical reaction optimization (CRO). It is an algorithm that is usually used to solve optimization problems. Solving optimization problems the algorithm gives better results than any other related metaheuristics. It can search the solution space locally as well as globally over a large population with the help of its four reaction operators. We are proposing a method to solve MCP by tuning all the initial parameters and redesigning four reaction operators of CRO. An additional repair operator is also designed to find optimal solutions in less computational time. Three benchmark datasets are used to observe the efficiency of the proposed algorithm. We obtained better results with less average errors in comparison to the state of art methods for the three datasets. For most of the graphs, the algorithm gives the best-known results mentioned in the datasets. The results are shown with the repair operator for all the datasets to understand the improvement in results clearly.

Suggested Citation

  • 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.
    • Handle: RePEc:spr:opsear:v:60:y:2023:i:3:d:10.1007_s12597-023-00654-z
    DOI: 10.1007/s12597-023-00654-z
    as

    Download full text from publisher

    File URL: http://link.springer.com/10.1007/s12597-023-00654-z
    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-023-00654-z?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. Neeraj Kumar Bhoi & Harpreet Singh & Saurabh Pratap & Pramod K. Jain, 2022. "Chemical reaction optimization algorithm for machining parameter of abrasive water jet cutting," OPSEARCH, Springer;Operational Research Society of India, vol. 59(1), pages 350-363, March.
    2. 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.
    3. Arijit De & Saurabh Pratap & Akhilesh Kumar & M. K. Tiwari, 2020. "A hybrid dynamic berth allocation planning problem with fuel costs considerations for container terminal port using chemical reaction optimization approach," Annals of Operations Research, Springer, vol. 290(1), pages 783-811, July.
    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. Raeesi, Ramin & Sahebjamnia, Navid & Mansouri, S. Afshin, 2023. "The synergistic effect of operational research and big data analytics in greening container terminal operations: A review and future directions," European Journal of Operational Research, Elsevier, vol. 310(3), pages 943-973.
    2. Meixian Jiang & Jiajia Feng & Jian Zhou & Lin Zhou & Fangzheng Ma & Guanghua Wu & Yuqiu Zhang, 2023. "Multi-Terminal Berth and Quay Crane Joint Scheduling in Container Ports Considering Carbon Cost," Sustainability, MDPI, vol. 15(6), pages 1-20, March.
    3. Jia, Shuai & Li, Chung-Lun & Xu, Zhou, 2020. "A simulation optimization method for deep-sea vessel berth planning and feeder arrival scheduling at a container port," Transportation Research Part B: Methodological, Elsevier, vol. 142(C), pages 174-196.
    4. Ayman Nagi & Meike Schroeder & Wolfgang Kersten, 2021. "Risk Management in Seaports: A Community Analysis at the Port of Hamburg," Sustainability, MDPI, vol. 13(14), pages 1-20, July.
    5. Xiaofang Wu & Hsi-Chi Yang, 2021. "An Ecological Sustainability Assessment Approach for Strategic Decision Making in International Shipping," Sustainability, MDPI, vol. 13(20), pages 1-18, October.
    6. João Luiz Marques Andrade & Gustavo Campos Menezes, 2023. "A column generation-based heuristic to solve the integrated planning, scheduling, yard allocation and berth allocation problem in bulk ports," Journal of Heuristics, Springer, vol. 29(1), pages 39-76, 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:spr:opsear:v:60:y:2023:i:3:d:10.1007_s12597-023-00654-z. 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.