# Exact and Heuristic Algorithms for Constrained Biclustering

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

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 13 of its 57 references that are in the map.
- First posted on arXiv 7 Aug 2025.

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

- [Convex optimization](https://mlsanity.com/paper/2106.01946/) (2021)
- [SDPNAL+: A Majorized Semismooth Newton-CG Augmented Lagrangian Method for Semidefinite Programming with Nonnegative Constraints](https://mlsanity.com/paper/1406.0942/) (2014)
- [Deterministic guarantees for Burer-Monteiro factorizations of smooth semidefinite programs](https://mlsanity.com/paper/1804.02008/) (2018)
- [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)
- [On the Burer-Monteiro method for general semidefinite programs](https://mlsanity.com/paper/1904.07147/) (2019)
- [The ratio-cut polytope and K-means clustering](https://mlsanity.com/paper/2006.15225/) (2020)
- [Size Matters: Cardinality-Constrained Clustering and Outlier Detection via Conic Optimization](https://mlsanity.com/paper/1705.07837/) (2017)
- [Complexity and performance of an Augmented Lagrangian algorithm](https://mlsanity.com/paper/1907.02401/) (2019)
- [Beyond Symmetry: Best Submatrix Selection for the Sparse Truncated SVD](https://mlsanity.com/paper/2105.03179/) (2021)
- [Global Optimization for Cardinality-constrained Minimum Sum-of-Squares Clustering via Semidefinite Programming](https://mlsanity.com/paper/2209.08901/) (2022)
- [A Semidefinite Programming-Based Branch-and-Cut Algorithm for Biclustering](https://mlsanity.com/paper/2403.11351/) (2024)
- [Fix and Bound: An efficient approach for solving large-scale quadratic programming problems with box constraints](https://mlsanity.com/paper/2211.08911/) (2022)

## Abstract (arXiv)

Biclustering, also known as co-clustering or two-way clustering, simultaneously partitions the rows and columns of a data matrix to reveal submatrices with coherent patterns. Incorporating background knowledge into clustering to enhance solution quality and interpretability has attracted growing interest in mathematical optimization and machine learning research. Extending this paradigm to biclustering enables prior information to guide the joint grouping of rows and columns. We study constrained biclustering with pairwise constraints, namely must-link and cannot-link constraints, which specify whether objects should belong to the same or different biclusters. As a model problem, we address the constrained version of the k-densest disjoint biclique problem, which aims to identify k disjoint complete bipartite subgraphs (called bicliques) in a weighted complete bipartite graph, maximizing the total density while satisfying pairwise constraints. We propose both exact and heuristic algorithms. The exact approach is a tailored branch-and-cut algorithm based on a low-dimensional semidefinite programming (SDP) relaxation, strengthened with valid inequalities and solved in a cutting-plane fashion. Exploiting integer programming tools, a rounding scheme converts SDP solutions into feasible biclusterings at each node. For large-scale instances, we introduce an efficient heuristic based on the low-rank factorization of the SDP. The resulting nonlinear optimization problem is tackled with an augmented Lagrangian method, where the subproblem is solved by decomposition through a block-coordinate projected gradient algorithm. Extensive experiments on synthetic and real-world datasets show that the exact method significantly outperforms general-purpose solvers, while the heuristic achieves high-quality solutions efficiently on large instances.