Algorithm to extract elements with largest sum from a matrix without repeating rows or columns?

user_125921 0
Viewed 939

I have a numeric matrix, and I need to extract the set of elements with the largest possible sum, subject to the constraint that no 2 elements can come from the same row or the same column. Is there any efficient algorithm for this, and is there an implementation of that algorithm for R?

For example, if the matrix is (using R's matrix notation):

     [,1] [,2] [,3]
[1,]    7    1    9
[2,]    8    4    2
[3,]    3    6    5

then the unique solution is [1,3], [2,1], [3,2], which extracts the numbers 9, 8, and 6 for a total of 23. However, if the matrix is:

     [,1] [,2] [,3]
[1,]    6    2    1
[2,]    4    9    5
[3,]    8    7    3

then there are 3 equally good solutions: 1,8,9; 3,6,9; and 5,6,7. These all add up to 18.

Additional notes:

  • If there are multiple equally good solutions, I need to find all of them. (Being able to find additional solutions that are almost as good would be useful as well, but not essential.)
  • The matrix elements are all non-negative, and many of them will be zero. Each row and column will contain at least 1 element that is nonzero.
  • The matrix can contain repeated elements.
  • The matrix need not be square. It might have more rows than columns or vice versa, but the constraint is always the same: no row or column may be used twice.
  • This problem could also be reformulated as finding a maximal-scoring set of edges between the 2 halves of a bipartite graph without re-using any node.
  • If it helps, you may assume that there is some small fixed k such that no row or column contains more than k non-zero values.

If anyone is curious, the rows of the matrix represent items to be labeled, the columns represent the labels, and each matrix element represents the "consistency score" for assigning a label to an item. I want to assign the each label to exactly one item in the way that maximizes the total consistency.

r matrix algorithm
2 Answers

My suggest would be to (1) find all the combinations of elements following the rule that in each combination, no two elements coming from the same row or same column (2) calculate the sum of elements in each combination (3) find the maximum sum and the corresponding combination.

Here I only show the square matrix case, the non-square matrix would follow similar idea.

(1) Suppose the matrix is n*n, keep the row order as 1 to n, all I need to do is to find all the permutations of columns index (1:n), after combine the row index and one permutation of columns index, then I would get the positions of elements in one combination that follow the rule, in this way I can identify the positions of elements in all the combinations.

matrix_data <- matrix(c(6,2,1,4,9,5,8,7,3), byrow=T,nrow = 3)
## example matrix

n_length <- dim(matrix_data)[1]
## row length

all_permutation <- permn(c(1:n_length))
## list of all the permutations of columns index

(2) Find sum of elements in each combination

index_func <- function(x){ ## x will be a permutation from the list all_permutation
  matrix_indexs <- matrix(data = c(c(1:n_length),x),
                         byrow = F, nrow = n_length)
  ## combine row index and column index to construct the positions of the elements in the matrix

  matrix_elements <- matrix_data[matrix_indexs]
  ## extract the elements based on their position

  matrix_combine <- cbind(matrix_indexs,matrix_elements)
  ## combine the above two matrices

  return(matrix_combine)
}


results <- sapply(all_permutation, sum(index_func(x)[,"matrix_elements"]))
## find the sums of all the combination

(3) Find the maximum sum and corresponding combination

max(results) ## 18 maximum sum is 18

max_index <- which(results==max(results)) ## 1 2 4 there are three combinations

## if you want the complete position index
lapply(all_permutation[max_index], index_func)

## output, first column is row index, second column is column index, last column is the corresponding matrix elements
[[1]]
         matrix_elements
[1,] 1 1               6
[2,] 2 2               9
[3,] 3 3               3

[[2]]
         matrix_elements
[1,] 1 1               6
[2,] 2 3               5
[3,] 3 2               7

[[3]]
         matrix_elements
[1,] 1 3               1
[2,] 2 2               9
[3,] 3 1               8
user_126477000

Here are 2 options:

1) Approaching this as an optimization problem where the objective function is to maximize the sum of elements chosen subject to the constraints that each row and column cannot be selected more than once.

sample data:

set.seed(0L)
m <- matrix(sample(12), nrow=4)
#m <- matrix(sample(16), nrow=4)
m

     [,1] [,2] [,3]
[1,]    9    2    6
[2,]    4    5   11
[3,]    7    3   12
[4,]    1    8   10

code:

library(lpSolve)
nr <- nrow(m)
nc <- ncol(m)

#create the indicator matrix for column indexes
colmat <- data.table::shift(c(rep(1, nr), rep(0, (nc-1)*nr)), seq(0, by=nr, length.out=nc), fill=0)
#create indicator matrix for row indexes
rowmat <- data.table::shift(rep(c(1, rep(0, nr-1)), nc), 0:(nr-1), fill=0)
A <- do.call(rbind, c(colmat, rowmat))

#call lp solver
res <- lp("max",
    as.vector(m),
    A,
    rep("<=", nrow(A)),
    rep(1, nrow(A)),
    all.bin=TRUE,
    num.bin.solns=3)

sample output:

which(matrix(res$solution[1:ncol(A)], nrow=nr)==1L, arr.ind=TRUE)
     row col
[1,]   1   1
[2,]   4   2
[3,]   3   3

2) And the above leads to an greedy heuristics approach to pick the largest element and eliminate the chosen row and column and then repeat on the smaller matrix:

v <- integer(min(nc, nr))
allix <- matrix(0, nrow=length(v), ncol=2)
for (k in seq_along(v)) {
    ix <- which(m == max(m), arr.ind=TRUE)
    allix[k,] <- ix
    v[k] <- m[ix]
    m <- m[-ix[1], -ix[2], drop=FALSE]
}
v
#[1] 12  9  8

But this does not lead to multiple solutions and hence not developing further to extract indices.

user_19894800
Related