期刊
EUROPEAN JOURNAL OF OPERATIONAL RESEARCH
卷 269, 期 3, 页码 834-843出版社
ELSEVIER SCIENCE BV
DOI: 10.1016/j.ejor.2018.03.010
关键词
Combinatorial optimization; Clique; Exact algorithms; Techniques for tight bounds; Mathematical formulation
资金
- China Scholarship Council
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.
作者
我是这篇论文的作者
点击您的名字以认领此论文并将其添加到您的个人资料中。
推荐
暂无数据