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

9 次查看（过去 30 天）
Adam McNamara
Adam McNamara 2016-9-8
编辑： Mudambi Srivatsa 2016-9-26
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
  1 个评论
Adam McNamara
Adam McNamara 2016-9-8
编辑：Adam McNamara 2016-9-8
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

请先登录，再进行评论。

请先登录，再回答此问题。

回答（1 个）

Mudambi Srivatsa
Mudambi Srivatsa 2016-9-26
编辑：Mudambi Srivatsa 2016-9-26
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.

类别

在 Help Center 和 File Exchange 中查找有关 Matrices and Arrays 的更多信息

标签

Community Treasure Hunt

Find the treasures in MATLAB Central and discover how the community can help you!

Start Hunting!

Translated by