IDEAS home Printed from https://ideas.repec.org/a/spr/annopr/v284y2020i1d10.1007_s10479-019-03159-5.html
   My bibliography  Save this article

A GPU based local search algorithm for the unweighted and weighted maximum s-plex problems

Author

Listed:
  • Bruno Nogueira

    (Universidade Federal de Alagoas)

  • Rian G. S. Pinheiro

    (Universidade Federal de Alagoas)

Abstract

Given a graph G(V, E) and a value $$s \in {\mathbb {N}}$$s∈N, an s-plex S is a subset of V such that each vertex $$v \in S$$v∈S has at least $$|S|-s$$|S|-s adjacent vertices in the subgraph induced by S. This work proposes a GPU based local search heuristic, called GPULS, for the problems of finding an s-plex of maximum cardinality and finding an s-plex of maximum weight. The proposed heuristic works well on both problems without any modification on its parameters or its code. GPULS considers two neighborhood structures, which are explored using tabu search and a first-improvement approach. We compare GPULS with the current best-performing exact methods and heuristics. The results obtained by GPULS are highly competitive, even when it runs on a CPU-only architecture. Moreover, we observed speedups of up to 16 times by running the heuristic on a hybrid CPU–GPU architecture.

Suggested Citation

  • Bruno Nogueira & Rian G. S. Pinheiro, 2020. "A GPU based local search algorithm for the unweighted and weighted maximum s-plex problems," Annals of Operations Research, Springer, vol. 284(1), pages 367-400, January.
    • Handle: RePEc:spr:annopr:v:284:y:2020:i:1:d:10.1007_s10479-019-03159-5
    DOI: 10.1007/s10479-019-03159-5
    as

    Download full text from publisher

    File URL: http://link.springer.com/10.1007/s10479-019-03159-5
    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/s10479-019-03159-5?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. Vladimir Boginski & Sergiy Butenko & Oleg Shirokikh & Svyatoslav Trukhanov & Jaime Gil Lafuente, 2014. "A network-based data mining approach to portfolio selection via weighted clique relaxations," Annals of Operations Research, Springer, vol. 216(1), pages 23-34, 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. Qinghua Wu & Jin-Kao Hao, 2013. "An adaptive multistart tabu search approach to solve the maximum clique problem," Journal of Combinatorial Optimization, Springer, vol. 26(1), pages 86-108, July.
    4. 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.
    5. Qinghua Wu & Jin-Kao Hao & Fred Glover, 2012. "Multi-neighborhood tabu search for the maximum weight clique problem," Annals of Operations Research, Springer, vol. 196(1), pages 611-634, July.
    6. Benjamin McClosky & Illya V. Hicks, 2012. "Combinatorial algorithms for the maximum k-plex problem," Journal of Combinatorial Optimization, Springer, vol. 23(1), pages 29-49, January.
    7. R. Martí & J. Marcos Moreno-Vega & A. Duarte, 2010. "Advanced Multi-start Methods," International Series in Operations Research & Management Science, in: Michel Gendreau & Jean-Yves Potvin (ed.), Handbook of Metaheuristics, chapter 0, pages 265-281, Springer.
    8. Pattillo, Jeffrey & Youssef, Nataly & Butenko, Sergiy, 2013. "On clique relaxation models in network analysis," European Journal of Operational Research, Elsevier, vol. 226(1), pages 9-18.
    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. Matteo Di Scipio & Mohammad Khan & Shihong Mao & Michael Chong & Conor Judge & Nazia Pathan & Nicolas Perrot & Walter Nelson & Ricky Lali & Shuang Di & Robert Morton & Jeremy Petch & Guillaume Paré, 2023. "A versatile, fast and unbiased method for estimation of gene-by-environment interaction effects on biobank-scale datasets," Nature Communications, Nature, vol. 14(1), pages 1-15, December.

    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. 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.
    2. Oleksandra Yezerska & Sergiy Butenko & Vladimir L. Boginski, 2018. "Detecting robust cliques in graphs subject to uncertain edge failures," Annals of Operations Research, Springer, vol. 262(1), pages 109-132, March.
    3. 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.
    4. Wayne Pullan, 2021. "Local search for the maximum k-plex problem," Journal of Heuristics, Springer, vol. 27(3), pages 303-324, June.
    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. 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.
    8. Timo Gschwind & Stefan Irnich & Isabel Podlinski, 2015. "Maximum Weight Relaxed Cliques and Russian Doll Search Revisited," Working Papers 1504, Gutenberg School of Management and Economics, Johannes Gutenberg-Universität Mainz, revised 19 May 2015.
    9. Vladimir Boginski & Sergiy Butenko & Oleg Shirokikh & Svyatoslav Trukhanov & Jaime Gil Lafuente, 2014. "A network-based data mining approach to portfolio selection via weighted clique relaxations," Annals of Operations Research, Springer, vol. 216(1), pages 23-34, May.
    10. Furini, Fabio & Ljubić, Ivana & Martin, Sébastien & San Segundo, Pablo, 2019. "The maximum clique interdiction problem," European Journal of Operational Research, Elsevier, vol. 277(1), pages 112-127.
    11. Alexander Veremyev & Oleg A. Prokopyev & Sergiy Butenko & Eduardo L. Pasiliao, 2016. "Exact MIP-based approaches for finding maximum quasi-cliques and dense subgraphs," Computational Optimization and Applications, Springer, vol. 64(1), pages 177-214, May.
    12. Balasundaram, Balabhaskar & Borrero, Juan S. & Pan, Hao, 2022. "Graph signatures: Identification and optimization," European Journal of Operational Research, Elsevier, vol. 296(3), pages 764-775.
    13. Zhuqi Miao & Balabhaskar Balasundaram, 2020. "An Ellipsoidal Bounding Scheme for the Quasi-Clique Number of a Graph," INFORMS Journal on Computing, INFORMS, vol. 32(3), pages 763-778, July.
    14. Timo Gschwind & Stefan Irnich & Fabio Furini & Roberto Wol?er Calvo, 2015. "Social Network Analysis and Community Detection by Decomposing a Graph into Relaxed Cliques," Working Papers 1520, Gutenberg School of Management and Economics, Johannes Gutenberg-Universität Mainz.
    15. Paolo Giudici & Gloria Polinesi & Alessandro Spelta, 2022. "Network models to improve robot advisory portfolios," Annals of Operations Research, Springer, vol. 313(2), pages 965-989, June.
    16. Timo Gschwind & Stefan Irnich & Fabio Furini & Roberto Wolfler Calvo, 2021. "A Branch-and-Price Framework for Decomposing Graphs into Relaxed Cliques," INFORMS Journal on Computing, INFORMS, vol. 33(3), pages 1070-1090, July.
    17. 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.
    18. Alex Gliesch & Marcus Ritt, 2022. "A new heuristic for finding verifiable k-vertex-critical subgraphs," Journal of Heuristics, Springer, vol. 28(1), pages 61-91, February.
    19. Justo Puerto & Moises Rodr'iguez-Madrena & Andrea Scozzari, 2019. "Location and portfolio selection problems: A unified framework," Papers 1907.07101, arXiv.org.
    20. 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.

    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:annopr:v:284:y:2020:i:1:d:10.1007_s10479-019-03159-5. 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.