Journal
EUROPEAN JOURNAL OF OPERATIONAL RESEARCH
Volume 269, Issue 3, Pages 834-843Publisher
ELSEVIER SCIENCE BV
DOI: 10.1016/j.ejor.2018.03.010
Keywords
Combinatorial optimization; Clique; Exact algorithms; Techniques for tight bounds; Mathematical formulation
Funding
- China Scholarship Council
Ask authors/readers for more resources
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 Branchand-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. (C) 2018 E(C)sevier B.V. All rights reserved.
Authors
I am an author on this paper
Click your name to claim this paper and add it to your profile.
Reviews
Recommended
No Data Available