How to select one value from each column and one value from each row and get minimal sum?

Hi all,

I wondered if anyone had any ideas with regard to the following problem?

I need to select 12 values from a 12x12 matrix with the minimum summed value. However I can only select one value from each column and one value from each row.

Previously matrix size was always less than 10 so I used perms to generate all the potential permutations and then selected the minimum.

However as the matrix gets larger the number of permutations becomes too large to consider this option.

I have played with the intlinprog but I cannot figure out the correct method.

Any ideas much appreciated,

Adam

[Adam McNamara]

For anyone finding this and wondering about the perms solution... see below:

MATLAB CODE
ncond=5;
M=rand(ncond);
possible_selections=perms(1:ncond);
  for jj=1:size(possible_selections,1)
s(jj)=sum(M(mat2vec([possible_selections(jj,:)' [1:ncond]'],[ncond ncond])));
  end
[~,best_selection_index]=min(s);
best_selection=possible_selections(best_selection_index,:);
% i.e., best_selection(1)= row to pick from column 1
%       best_selection(2)= row to pick from column 2 ...

This requires the following function which is my homebaked version of something I am sure can be done in a much easier way. It outputs the index values of a matrix if you know the row and column values and size of the matrix, or vice versa.

MATLAB CODE
function [out] = mat2vec(rowcol,msize);
if size(rowcol,2) == 2
out = (rowcol(:,2)*msize(1))-(msize(1)-rowcol(:,1));
else
out = zeros(length(rowcol),2);
fl= floor(rowcol/msize(1));
o1=rowcol/msize(1)-fl;
out(find(o1 == 0),2) = fl(find(o1 == 0)); 
out(find(o1 == 0),1) = msize(1); 
out(find(o1 ~= 0),2) = fl(find(o1 ~= 0))+1; 
out(find(o1 ~= 0),1) = round(o1(find(o1 ~= 0)).*msize(1));
end

Answer 1

[Mudambi Srivatsa]

I understand that you are trying to minimize the sum of elements in a matrix under the condition that only one value from each column and one value from each row is selected. As matrix grows large, the brute force approach takes too much time as the number of permutations becomes too large. Instead, you can use a standard algorithm such as Hungarian/Munkres algorithm that solve the problem faster.

Refer to the following MATLAB implementation of the algorithm for reference:

Hungarian/Munkres File Exchange

To call the function to get the element indices and the minimized sum, use the following syntax:

[ASSIGN,COST] = munkres(M);

where M is your input matrix, ASSIGN is the array of column indices and COST is the minimum sum.

Note that as opposed to the row indices in your code; the above implementation outputs column indices for the rows. You can modify the function to suit your needs. For any additional questions regarding the file exchange submission, contact the author of the file exchange submission.