The Maximum Weighted Submatrix Coverage Problem: A CP Approach

Derval, Guillaume [UCL] Branders, Vincent [UCL] Dupont, Pierre [UCL] Schaus, Pierre [UCL]

The objective of the maximum weighted submatrix coverage problem (MWSCP) is to discover K submatrices that together cover the largest sum of entries of the input matrix. The special case of K = 1 called the maximal-sum submatrix problem was successfully solved with CP. Unfortunately, the case of K > 1 is more difficult to solve as the selection of the rows of the submatrices cannot be decided in polynomial time solely from the selection of K sets of columns. The search space is thus substantially augmented compared to the case K = 1. We introduce a complete CP approach for solving this problem efficiently composed of the major CP ingredients: (1) filtering rules, (2) a lower bound, (3) dominance rules, (4) variable-value heuristic, and (5) a large neighborhood search. As the related biclustering problem, MWSCP has many practical data-mining applications such as gene module discovery in bioinformatics. Through multiple experiments on synthetic and real datasets, we provide evidence of the practicality of the approach both in terms of computational time and quality of the solutions discovered.