A new integer linear programming formulation for the maximum balanced Bi-clique problem

The Maximum Balanced Biclique (MBB) problem in bipartite graphs, pertinent to bioinformatics applications such as protein–protein interaction networks and gene expression analysis, seeks the largest complete bipartite subgraph with equal-sized vertex sets. Recognized as NP-hard, Integer Linear Programming (ILP) offers an exact solution approach. This study presents a new ILP formulation that combines the advantages of two prior formulations, achieving both a reduced number of variables and a compact set of constraints. Experimental evaluations on random and real-world bipartite graphs demonstrate improved computation times, particularly for graphs with tall adjacency matrices and densities between 0.05 and 0.30 in small-size instances. Additionally, we introduce a pruning lemma that enables safe vertex elimination without compromising optimality, and a polynomial-time local search algorithm. Together, these components constitute the FindMBB algorithm, which effectively solves the MBB problem in practice across a broad range of inputs.