Maximal-Sum submatrix search using a hybrid contraint programming/linear programming approach

A Maximal-Sum Submatrix (MSS) maximizes the sum of the entries corresponding to the Cartesian product of a subset of rows and columns from an original matrix (with positive and negative entries). Despite being NP-hard, this recently introduced problem was already proven to be useful for practical data mining applications. It was used for identifying bi-clusters in gene expression data or to extract a sub matrix that is then visualized in a circular plot. The state-of-the-art results for MSS are obtained using an advanced Constraint Programing approach that combines a custom filtering algorithm with a Large Neighborhood Search. We improve the state-of-the-art approach by introducing new upper bounds based on linear and mixed-integer programming formulations, along with dedicated pruning algorithms. We experiment on both synthetic and real-life data, and show that our approach outperforms the previous methods. (c) 2021 Elsevier B.V. All rights reserved.

Automated summary

The Maximal-Sum Submatrix problem maximizes the sum of entries in a subset of rows and columns from an original matrix. Despite being NP-hard, it has practical applications in data mining. State-of-the-art results have been achieved by combining Constraint Programming with custom algorithms, but this study introduces new upper bounds and pruning algorithms to further improve the approach, showing better performance on both synthetic and real-life data.