EURO 2024 Copenhagen
Abstract Submission

EURO-Online login

785. A branch-and-cut algorithm for biclustering via semidefinite programming

Invited abstract in session MA-32: Large Scale Constrained Optimization: Algorithms and Applications, stream Advances in large scale nonlinear optimization.

Monday, 8:30-10:00
Room: 41 (building: 303A)

Authors (first author is the speaker)

1. Antonio M. Sudoso
Sapienza University of Rome

Abstract

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. Focusing on the densest k-disjoint-biclique problem as a biclustering model, the objective is to identify a set of k disjoint bicliques within a weighted complete bipartite graph such that the sum of the densities of the complete subgraphs induced by these bicliques is maximized. A branch-and-cut method is proposed to achieve global optimality. The upper bound routine involves solving a semidefinite programming relaxation, employing a cutting-plane approach to strengthen the bound. For the lower bound, a maximum weight matching rounding procedure is designed, leveraging the solution of the relaxation solved at each node. Computational results on both synthetic and real-world instances show that the proposed algorithm is capable of solving instances with a size ten times larger than general-purpose solvers.

Keywords

Status: accepted

Back to the list of papers