zbMATH — the first resource for mathematics

The maximum weighted submatrix coverage problem: a CP approach. (English) Zbl 07116698
Rousseau, Louis-Martin (ed.) et al., Integration of constraint programming, artificial intelligence, and operations research. 16th international conference, CPAIOR 2019, Thessaloniki, Greece, June 4–7, 2019. Proceedings. Cham: Springer (ISBN 978-3-030-19211-2/pbk; 978-3-030-19212-9/ebook). Lecture Notes in Computer Science 11494, 258-274 (2019).
Summary: 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.
For the entire collection see [Zbl 1410.68020].
MSC:
 68T20 Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.) 90C27 Combinatorial optimization
Full Text: