mssm.search.cpgc: Searches for a Max-Sum Submatrix using CPGC

In vbranders/mssm: Sub-Matrix of Maximal Sum identification, Scala implementation wrapped in R

Description

Searches for a submatrix of maximal sum using a Constraint Programming with Global Constraint approach. See Details section for informations on the search performed and the criterion required to complete it.

Usage

mssm.search.cpgc(x, budget = 10, convergence = "time",
  verbose = FALSE, lowerBound = 0, lightFilter = FALSE,
  variableOrdering = NULL, lns = FALSE, lns.nRestarts = 100,
  lns.failureLimit = 500, lns.maxDiscrepancy = 2,
  lns.restartFilter = 70)

Arguments

x	a matrix or a Java two-dimensionnal array of double (mssm.asJavaMatrix()).
budget	a limit to prevent long searches. Its value is used in combination with parameter convergence. It corresponds either to the maximum number of solutions without improvement of the sum (if convergence == "solution") or the maximum number of seconds without improvements of the sum (if convergence == "time"). See details of convergence.
convergence	indicates criterions to abort the search. It can be any of the following: "none" or -1 The search is not aborted. It will stop only when completed, which means that the solution is optimal (if lns == FALSE) or all lns restarts are done. "solution" or 0 If the last budget solutions identified did not improve the sum, the search is aborted. "time" or 1 Abort the search if budget seconds have elapsed since the last improving solution was found. This is the default value.
verbose	indicates whether improving solutions should be printed or not.
lowerBound	is the expected minimum sum ot the submatrix to find. No submatrix with sum below lowerBound will be considered as a solution to store. Raising its value might improve the filtering of non-optimal solution. This however can be diffucult to estimate and a value above the optimal sum will prevent the identification of any solution.
lightFilter	reduces the computational cost of pruning the search tree at the expense of a reduced filtering (if lightFilter == TRUE). It is preferable to set it to FALSE for very large matrices as one prefer a stronger filtering of sub-optimal solutions, even at the expense of some additional computations.
variableOrdering	is an ordering of the columns indices. It indicates which columns should be considered first for the branching. A NULL value is associated to the natural ordering (1:j if javaMatrix has j columns). It appears that columns with many positive entries should be considered first in the search. See mssm.getHeuristicReordering() as an example of column ordering.
lns	allows the use of a large neighborhood search: after a given number lns.failureLimit of backtracking (non improving solutions), the search is restarted while fixing lns.restartFilter percent of the columns of the best solution found so far.
lns.nRestarts	is the number of restarts to perform if lns is TRUE.
lns.failureLimit	is the number of backtracks allowed for each large neighborhood search.
lns.maxDiscrepancy	is a limite on the number of discrepancies. In the search tree, a discrepancy is counted whenever one explores the right child of a node. Small values prevent the search of the full tree but visit only the left-most branches. This should be considered when you are confident with the variable ordering (see parameter variableOrdering).
lns.restartFilter	is the percentage of the columns of the best solution found so far to keep in subsequent search. More precisely, at each lns restart, lns.restartFilter/100 of the columns of the best solution are fixed and the search is performed on the non-fixed columns.

Details

This function performs the search of a submatrix of maximal sum accordingly to its arguments. A submatrix is a rectangular, non-necessarily contiguous, subset of rows and of columns of a (larger) matrix. A submatrix is of maximal sum if the sum of its entires (selected from the original matrix) is of maximal sum. The search is completed whenever it finds a provably optimal solution. If parameter lns is TRUE, the search is completed whenever the lns.nRestarts restarts have been done. For some scenarios, one might wants to abort the search before completion. This is doable through the combination of parameters budget and convergence.

Value

A submatrix of maximal sum, represented as a list, with the associated sum, columns and rows.

Maintainer

Vincent Branders <[e-mail]>.

See Also

mssm.asJavaMatrix() and mssm.loadMatrix() to transform a matrix to a Java matrix and to load a Java matrix from a file. See also mssm.getHeuristicReordering() for an heuristic ordering of the columns. See also package mssm.

vbranders/mssm documentation built on Aug. 1, 2020, 11:45 a.m.