Files

ds2019-colgen-matrix.pdf
  • Open Access
  • Adobe PDF
  • 438.63 KB
Download

Details

Authors
Abstract
The objective of the maximum weighted set of disjoint submatrices problem is to discover K disjoint submatrices that together cover the largest sum of entries of an input matrix. It has many practical data-mining applications, as the related biclustering problem, such as gene module discovery in bioinformatics. It differs from the maximum-weighted submatrix coverage problem introduced in [6] by the explicit formulation of disjunction constraints: submatrices must not overlap. In other words, all matrix entries must be covered by at most one submatrix. The particular case of 𝐾=1, called the maximal-sum submatrix problem, was successfully tackled with constraint programming in [5]. Unfortunately, the case of 𝐾>1 is more challenging to solve as the selection of rows cannot be decided in polynomial time solely from the selection of K sets of columns. It can be proved to be NP-hard. We introduce a hybrid column generation approach using constraint programming to generate columns. It is compared to a standard mixed integer linear programming (MILP) through experiments on synthetic datasets. Overall, fast and valuable solutions are found by column generation while the MILP approach cannot handle a large number of variables and constraints.
Affiliations

Citations

  • APA
  • Chicago
  • FWB

Branders, V., Derval, G., Schaus, P., & Dupont, P. (2019). Mining a Maximum Weighted Set of Disjoint Submatrices. Discovery Science : Lecture Notes in Computer Science, p. 18-28. https://doi.org/10.1007/978-3-030-33778-0_2