IDEAS home Printed from https://ideas.repec.org/a/spr/jglopt/v59y2014i1p1-21.html
   My bibliography  Save this article

Speeding up branch and bound algorithms for solving the maximum clique problem

Author

Listed:
  • Evgeny Maslov
  • Mikhail Batsyn
  • Panos Pardalos

Abstract

In this paper we consider two branch and bound algorithms for the maximum clique problem which demonstrate the best performance on DIMACS instances among the existing methods. These algorithms are MCS algorithm by Tomita et al. ( 2010 ) and MAXSAT algorithm by Li and Quan ( 2010a , b ). We suggest a general approach which allows us to speed up considerably these branch and bound algorithms on hard instances. The idea is to apply a powerful heuristic for obtaining an initial solution of high quality. This solution is then used to prune branches in the main branch and bound algorithm. For this purpose we apply ILS heuristic by Andrade et al. (J Heuristics 18(4):525–547, 2012 ). The best results are obtained for p_hat1000-3 instance and gen instances with up to 11,000 times speedup. Copyright Springer Science+Business Media New York 2014

Suggested Citation

  • 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.
    • Handle: RePEc:spr:jglopt:v:59:y:2014:i:1:p:1-21
    DOI: 10.1007/s10898-013-0075-9
    as

    Download full text from publisher

    File URL: http://hdl.handle.net/10.1007/s10898-013-0075-9
    Download Restriction: Access to full text is restricted to subscribers.
    File URL: https://libkey.io/10.1007/s10898-013-0075-9?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. Jenelius, Erik & Petersen, Tom & Mattsson, Lars-Göran, 2006. "Importance and exposure in road network vulnerability analysis," Transportation Research Part A: Policy and Practice, Elsevier, vol. 40(7), pages 537-560, August.
    2. Butenko, S. & Wilhelm, W.E., 2006. "Clique-detection models in computational biochemistry and genomics," European Journal of Operational Research, Elsevier, vol. 173(1), pages 1-17, August.
    3. Anna Nagurney (ed.), 2003. "Innovations in Financial and Economic Networks," Books, Edward Elgar Publishing, number 3116.
    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. Yuichi Asahiro & Tomohiro Kubo & Eiji Miyano, 2019. "Experimental Evaluation of Approximation and Heuristic Algorithms for Maximum Distance-Bounded Subgraph Problems," The Review of Socionetwork Strategies, Springer, vol. 13(2), pages 143-161, October.
    2. 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.
    3. Coniglio, Stefano & Furini, Fabio & San Segundo, Pablo, 2021. "A new combinatorial branch-and-bound algorithm for the Knapsack Problem with Conflicts," European Journal of Operational Research, Elsevier, vol. 289(2), pages 435-455.
    4. San Segundo, Pablo & Furini, Fabio & Álvarez, David & Pardalos, Panos M., 2023. "CliSAT: A new exact algorithm for hard maximum clique problems," European Journal of Operational Research, Elsevier, vol. 307(3), pages 1008-1025.
    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. 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.

    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. 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.
    2. Zhang, Nan & Huang, Hong & Su, Boni & Zhao, Jinlong, 2015. "Analysis of dynamic road risk for pedestrian evacuation," Physica A: Statistical Mechanics and its Applications, Elsevier, vol. 430(C), pages 171-183.
    3. Cats, Oded & Jenelius, Erik, 2015. "Planning for the unexpected: The value of reserve capacity for public transport network robustness," Transportation Research Part A: Policy and Practice, Elsevier, vol. 81(C), pages 47-61.
    4. Mengying Cui & David Levinson, 2018. "Accessibility analysis of risk severity," Transportation, Springer, vol. 45(4), pages 1029-1050, July.
    5. Dowds, Jonathan & Aultman-Hall, Lisa, 2015. "Challenges and Opportunities for Integrating Climate Adaptation Efforts across State, Regional and Local Transportation Agencies," Institute of Transportation Studies, Working Paper Series qt5t88h66m, Institute of Transportation Studies, UC Davis.
    6. Bucar, Raif C.B. & Hayeri, Yeganeh M., 2020. "Quantitative assessment of the impacts of disruptive precipitation on surface transportation," Reliability Engineering and System Safety, Elsevier, vol. 203(C).
    7. Jenelius, Erik, 2010. "User inequity implications of road network vulnerability," The Journal of Transport and Land Use, Center for Transportation Studies, University of Minnesota, vol. 2(3), pages 57-73.
    8. Mohamad Darayi & Kash Barker & Joost R. Santos, 2017. "Component Importance Measures for Multi-Industry Vulnerability of a Freight Transportation Network," Networks and Spatial Economics, Springer, vol. 17(4), pages 1111-1136, December.
    9. Foad Mahdavi Pajouh, 2020. "Minimum cost edge blocker clique problem," Annals of Operations Research, Springer, vol. 294(1), pages 345-376, November.
    10. Svyatoslav Trukhanov & Chitra Balasubramaniam & Balabhaskar Balasundaram & Sergiy Butenko, 2013. "Algorithms for detecting optimal hereditary structures in graphs, with application to clique relaxations," Computational Optimization and Applications, Springer, vol. 56(1), pages 113-130, September.
    11. Jenelius, Erik & Mattsson, Lars-Göran, 2012. "Road network vulnerability analysis of area-covering disruptions: A grid-based approach with case study," Transportation Research Part A: Policy and Practice, Elsevier, vol. 46(5), pages 746-760.
    12. Baroud, Hiba & Barker, Kash & Ramirez-Marquez, Jose E. & Rocco S., Claudio M., 2014. "Importance measures for inland waterway network resilience," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 62(C), pages 55-67.
    13. Safirova, Elena & Gillingham, Kenneth & Houde, Sébastien, 2007. "Measuring marginal congestion costs of urban transportation: Do networks matter?," Transportation Research Part A: Policy and Practice, Elsevier, vol. 41(8), pages 734-749, October.
    14. Tony H. Grubesic & Timothy C. Matisziw, 2008. "Prospects for Assessing and Managing Vulnerable Infrastructures: Policy and Practice," Growth and Change, Wiley Blackwell, vol. 39(4), pages 543-547, December.
    15. Erik Jenelius & Lars-Göran Mattsson, 2011. "The impact of network density, travel and location patterns on regional road network vulnerability," ERSA conference papers ersa10p448, European Regional Science Association.
    16. 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.
    17. Rolf Nyberg & Magnus Johansson, 2013. "Indicators of road network vulnerability to storm-felled trees," Natural Hazards: Journal of the International Society for the Prevention and Mitigation of Natural Hazards, Springer;International Society for the Prevention and Mitigation of Natural Hazards, vol. 69(1), pages 185-199, October.
    18. Veremyev, Alexander & Boginski, Vladimir & Pasiliao, Eduardo L. & Prokopyev, Oleg A., 2022. "On integer programming models for the maximum 2-club problem and its robust generalizations in sparse graphs," European Journal of Operational Research, Elsevier, vol. 297(1), pages 86-101.
    19. Bell, Michael G.H. & Kurauchi, Fumitaka & Perera, Supun & Wong, Walter, 2017. "Investigating transport network vulnerability by capacity weighted spectral analysis," Transportation Research Part B: Methodological, Elsevier, vol. 99(C), pages 251-266.
    20. Ling Zhang & Jingjing Hao & Xiaofeng Ji & Lan Liu, 2019. "Research on the Complex Characteristics of Freight Transportation from a Multiscale Perspective Using Freight Vehicle Trip Data," Sustainability, MDPI, vol. 11(7), pages 1-20, March.

    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:jglopt:v:59:y:2014:i:1:p:1-21. 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.