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

arXiv: https://arxiv.org/abs/2403.11351 · HTML: https://mlsanity.com/paper/2403.11351/

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- Builds on 10 of its 38 references that are in the map.
- First posted on arXiv 17 Mar 2024.

## Builds on (most cited first, 10 of 10)

- [SDPNAL+: A Majorized Semismooth Newton-CG Augmented Lagrangian Method for Semidefinite Programming with Nonnegative Constraints](https://mlsanity.com/paper/1406.0942/) (2014)
- [SOS-SDP: an Exact Solver for Minimum Sum-of-Squares Clustering](https://mlsanity.com/paper/2104.11542/) (2021)
- [An Exact Algorithm for Semi-supervised Minimum Sum-of-Squares Clustering](https://mlsanity.com/paper/2111.15571/) (2021)
- [SDPNAL+: A Matlab software for semidefinite programming with bound constraints (version 1.0)](https://mlsanity.com/paper/1710.10604/) (2017)
- [Solving sparse principal component analysis with global support](https://mlsanity.com/paper/2010.11152/) (2020)
- [Beyond Symmetry: Best Submatrix Selection for the Sparse Truncated SVD](https://mlsanity.com/paper/2105.03179/) (2021)
- [A Convergent 3-Block Semi-Proximal Alternating Direction Method of Multipliers for Conic Programming with 4-Type of Constraints](https://mlsanity.com/paper/1404.5378/) (2014)
- [Sparse PCA on fixed-rank matrices](https://mlsanity.com/paper/2201.02487/) (2022)
- [ADMM for the SDP relaxation of the QAP](https://mlsanity.com/paper/1512.05448/) (2015)
- [Global Optimization for Cardinality-constrained Minimum Sum-of-Squares Clustering via Semidefinite Programming](https://mlsanity.com/paper/2209.08901/) (2022)

## Built on by (most cited first, 2 of 2)

- [Exact and Heuristic Algorithms for Constrained Biclustering](https://mlsanity.com/paper/2508.05493/) (2025)
- [Provably Finding a Hidden Dense Submatrix among Many Planted Dense Submatrices via Convex Programming](https://mlsanity.com/paper/2601.03946/) (2026)

## Abstract (arXiv)

Biclustering, also called co-clustering, block clustering, or two-way clustering, involves the simultaneous clustering of both the rows and 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.