Matrix Max Sum

Hello, I am trying to understand a way to find a 'matrix max sum' while each element being the maximum possible value and also being the 'only one' in its entire row and column.

thanks for your help

Ex:

      7  53 183 439 863
    497 383 563  79 973    
    287  63 343 169 583
    627 343 773 959 943    
    767 473 103 699 303

The output should result in the sum of: (767+53+343+959+973)=3095

[Richard Brown]

What's the largest size matrix that you'll need to consider?

[Oleg Komarov]

The criteria you described do not match with your example.

"Each element being the maximum possible value" in the row or column?

"also being the 'only one' in its entire row and column", then why 53 and not 473?

Actually, it seems all values are unique.

[Richard Brown]

He/she means that you need to choose 5 entries, none of which sharing the same row or column, that have the maximum possible sum

[Oleg Komarov]

@Richard: thanks.

Answer 1

[Walter Roberson]

Form the permutations of 1:5. For each permutation, let the row numbers be 1:5 and the column numbers be the individual permutation, and index into the data matrix and sum the resulting values across the second dimension. The maximum result along the first dimension is then the maximum value, and you can reconstruct the individual values from the permutation corresponding to the max value. (Hint: you will probably use sub2ind along the way.)

[Richard Brown]

But good luck using this method for n bigger than about 10 :)

Answer 2

[Geoff]

If I understand your question correctly, you must pick a value from each row/column such that you never use a row or column more than once. In addition, you are not allowed to pick a value that has already been picked (for example the number 343 is duplicate).

This is a global optimisation problem. There may be clever algorithms out there that can solve it in less than factorial time, but effectively what you need to do is check every permutation.

Let's say we permute the rows:

rows = perms(1:5);

Then it's just a case of examining the diagonal of any particular permutation. You want to find which permutation yields the maximum diagonal sum using unique values.

This is easily (but not necessarily) done in a loop.

M = [7  53 183 439 863
   497 383 563  79 973
   287  63 343 169 583
   627 343 773 959 943
   767 473 103 699 303 ];

for n = 1:size(rows,1)
  d = diag(M(rows(n,:), :));
  ...
end

Now fill in the blanks. Is this a homework problem? I should stop there. =)

Functions you may need: unique, sum, max

You might want to generate your sums into a matrix and then choose the max value of that matrix after the loop.

Incidentally, I get the result: 3315

   767   383   343   959   863

For this matrix, it doesn't matter whether you check for uniqueness of a value or not.

-g-

Answer 3

[James Tursa]

It was an interesting question, so I did a mex implementation. Uses a brute force indexing scheme with rejection (i.e., goes through all possible index sets and rejects the ones with duplicate row values). This takes a long time to run even for moderately small size inputs. Hope your real problem isn't too large.

/* File: maxmatrix.c                                                       */
/* Computes the max sum of matrix elements, one element per row and column */
/* Uses brute force indexing scheme with rejection. Not the fastest.       */
/* Programmer: James Tursa                                                 */
/* [X I] = maxmatrix(M)                                                    */
/*  M = double full square matrix                                          */
/*  X = the calculated max sum                                             */
/*  I = the linear indexes of the elements used for the max sum (optional) */

#include "mex.h"
void mexFunction(int nlhs, mxArray *plhs[], int nrhs, const mxArray *prhs[])
{
    mwSize *ix;
  mwSize i, j, m, n;
  double *pr, *jx = NULL;
  double d, dmax = -mxGetInf();
  int ok;

  if( nrhs != 1 || !mxIsDouble(prhs[0]) || mxGetNumberOfDimensions(prhs[0]) != 2 ||
    (m=mxGetM(prhs[0])) != (n=mxGetN(prhs[0])) || mxIsEmpty(prhs[0]) ) {
    mexErrMsgTxt("Expected one non-empty double square matrix input.");
  }
  if( nlhs > 2 ) {
    mexErrMsgTxt("Too many outputs.");
  }
  pr = mxGetPr(prhs[0]);
  ix = mxMalloc((m+1)*sizeof(*ix));
  if( nlhs == 2 ) {
    plhs[1] = mxCreateDoubleMatrix(1,m,mxREAL);
    jx = mxGetPr(plhs[1]);
  }
  for( i=0; i<=m; i++ ) {
    ix[i] = 0;
  }
  while( !ix[m] ) {
    ok = 1;
    for( i=0; i<m-1 && ok; i++ ) {
      for( j=i+1; j<m && ok; j++ ) {
        if( ix[i] == ix[j] ) {
          ok = 0;
        }
      }
    }
    if( ok ) {
      d = 0.0;
      for( i=0; i<m; i++ ) {
        d += pr[ix[i] + i * m];
      }
      if( d > dmax ) {
        dmax = d;
        if( jx ) {
          for( i=0; i<m; i++ ) {
              jx[i] = 1 + ix[i] + i * m;
          }
        }
      }
    }
    ix[0]++;
    for( i=0; i<m; i++ ) {
      if( ix[i] == m ) {
        ix[i] = 0;
        ix[i+1]++;
      } else {
        break;
      }
    }
  }
  mxFree(ix);
  plhs[0] = mxCreateDoubleScalar(dmax);
}