IDEAS home Printed from https://ideas.repec.org/a/eee/ejores/v269y2018i3p834-843.html
   My bibliography  Save this article

Towards effective exact methods for the Maximum Balanced Biclique Problem in bipartite graphs

Author

Listed:
  • Zhou, Yi
  • Rossi, André
  • Hao, Jin-Kao

Abstract

The Maximum Balanced Biclique Problem (MBBP) is a prominent model with numerous applications. Yet, the problem is NP-hard and thus computationally challenging. We propose novel ideas for designing effective exact algorithms for MBBP in bipartite graphs. First, an Upper Bound Propagation (UBP) procedure to pre-compute an upper bound involving each vertex is introduced. Then we extend a simple Branch-and-Bound (B&B) algorithm by integrating the pre-computed upper bounds. Based on UBP, we also study a new integer linear programming model of MBBP which is more compact than an existing formulation (Dawande, Keskinocak, Swaminathan, & Tayur, 2001). We introduce new valid inequalities induced from the upper bounds to tighten these mathematical formulations for MBBP. Experiments with random bipartite graphs demonstrate the efficiency of the extended B&B algorithm and the valid inequalities generated on demand. Further tests with 30 real-life instances show that, for at least three very large graphs, the new approaches improve the computational time with four orders of magnitude compared to the original B&B.

Suggested Citation

  • 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.
    • Handle: RePEc:eee:ejores:v:269:y:2018:i:3:p:834-843
    DOI: 10.1016/j.ejor.2018.03.010
    as

    Download full text from publisher

    File URL: http://www.sciencedirect.com/science/article/pii/S0377221718302194
    Download Restriction: Full text for ScienceDirect subscribers only
    File URL: https://libkey.io/10.1016/j.ejor.2018.03.010?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. Zhou, Yi & Hao, Jin-Kao & Goëffon, Adrien, 2017. "PUSH: A generalized operator for the Maximum Vertex Weight Clique Problem," European Journal of Operational Research, Elsevier, vol. 257(1), pages 41-54.
    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. 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.
    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. 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.

    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. Filipa D. Carvalho & Maria Teresa Almeida, 2017. "The triangle k-club problem," Journal of Combinatorial Optimization, Springer, vol. 33(3), pages 814-846, April.
    3. 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.
    4. Li, Chu-Min & Liu, Yanli & Jiang, Hua & Manyà, Felip & Li, Yu, 2018. "A new upper bound for the maximum weight clique problem," European Journal of Operational Research, Elsevier, vol. 270(1), pages 66-77.
    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. 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.
    7. 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.
    8. Laurent, Monique & Vargas, Luis Felipe, 2022. "Finite convergence of sum-of-squares hierarchies for the stability number of a graph," Other publications TiSEM 3998b864-7504-4cf4-bc1d-f, Tilburg University, School of Economics and Management.
    9. Lehouillier, Thibault & Omer, Jérémy & Soumis, François & Desaulniers, Guy, 2017. "Two decomposition algorithms for solving a minimum weight maximum clique model for the air conflict resolution problem," European Journal of Operational Research, Elsevier, vol. 256(3), pages 696-712.
    10. Foad Mahdavi Pajouh, 2020. "Minimum cost edge blocker clique problem," Annals of Operations Research, Springer, vol. 294(1), pages 345-376, November.
    11. François Fulconis & Didier Bédé & Laurence Saglietto & Joice de Almeira Goes & Gilles Paché & Raymundo Forradelas, 2014. "The entry of logistics service provider (LSP) into the wine industry supply chain," Post-Print hal-01062817, HAL.
    12. Zhou, Yi & Hao, Jin-Kao & Goëffon, Adrien, 2017. "PUSH: A generalized operator for the Maximum Vertex Weight Clique Problem," European Journal of Operational Research, Elsevier, vol. 257(1), pages 41-54.
    13. 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.
    14. 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.
    15. Luzhi Wang & Shuli Hu & Mingyang Li & Junping Zhou, 2019. "An Exact Algorithm for Minimum Vertex Cover Problem," Mathematics, MDPI, vol. 7(7), pages 1-8, July.
    16. Alessio Troiani, 2024. "Probabilistic Cellular Automata Monte Carlo for the Maximum Clique Problem," Mathematics, MDPI, vol. 12(18), pages 1-16, September.
    17. Yang Wang & Jin-Kao Hao & Fred Glover & Zhipeng Lü & Qinghua Wu, 2016. "Solving the maximum vertex weight clique problem via binary quadratic programming," Journal of Combinatorial Optimization, Springer, vol. 32(2), pages 531-549, August.
    18. Zhong, Haonan & Mahdavi Pajouh, Foad & A． Prokopyev, Oleg, 2023. "On designing networks resilient to clique blockers," European Journal of Operational Research, Elsevier, vol. 307(1), pages 20-32.
    19. 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.
    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:eee:ejores:v:269:y:2018:i:3:p:834-843. 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: Catherine Liu (email available below). General contact details of provider: http://www.elsevier.com/locate/eor .

    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.