A Semidefinite Programming-Based Branch-and-Cut Algorithm for Biclustering

Biclustering, also called co-clustering, block clustering, or two-way clustering, involves the simultaneous clustering of both the rows and the columns of a data matrix into distinct groups such that the rows and columns within a group display similar patterns. As a model problem for biclustering, we consider the k-densest disjoint biclique problem, whose goal is to identify k disjoint complete bipartite subgraphs (called bicliques) of a given weighted complete bipartite graph such that the sum of their densities is maximized. To address this problem, we present a tailored branch-and-cut algorithm. For the upper-bound routine, we consider a semidefinite programming relaxation and propose valid inequalities to strengthen the bound. We solve this relaxation in a cutting-plane fashion using a first-order method. For the lower bound, we design a maximum weight matching rounding procedure that exploits the solution of the relaxation solved at each node. Computational results on both synthetic and real-world instances show that the proposed algorithm can solve instances approximately 20 times larger than those handled by general-purpose solvers. History: Accepted by Antonio Frangioni, Area Editor for Design & Analysis of Algorithms–Continuous. Supplemental Material: The software that supports the findings of this study is available within the paper and its Supplemental Information ( https://pubsonline.informs.org/doi/suppl/10.1287/ijoc.2024.0683 ) as well as from the IJOC GitHub software repository ( https://github.com/INFORMSJoC/2024.0683 ). The complete IJOC Software and Data Repository is available at https://informsjoc.github.io/ .