Finding minimum from matrix

Question

Consider following $3\times 3$ matrix.

$\begin{pmatrix}3&6&9\\ 2& 4 &8\\ 1 &5& 7 \end{pmatrix}$

I need to find combination of three numbers where each number comes from unique column & row. For example $3,6,8$ is not what I want as $3$ and $6$ are from same row.

$6,4,7$ is also not right because $6$ and $4$ are from same columns.

$3,4,7$ is valid as each number comes from different column and row.

Next thing I want, is to find combination whose sum is minimum compared to sum of all other possible combinations. For example $3,4,7$ will be final answer if $3+4+7 = \min$. How do I find this for $n \times n$ matrix?

Answer 1

This is known as the assignment problem. The best-known algorithm for solving it is the Hungarian algorithm.

Answer 2

Per the previous answer, this is a linear assignment problem. Here is a simple way to solve it (not necessarily the fastest executing for very large n).

If you have MATLAB, you can download YALMIP for free.

Let A = n by n matrix of interest.

x = binvar(n,n,'full') % x defined to be a not necessarily symmetric n by n matrix of zeros and ones, which is the matrix of optimization variables specifying which entries of A are to be chosen (1 if chosen, 0 if not).

optimize([sum(x,2) == 1, sum(x,1) == 1],sum(sum(x.*A))) % Solves the problem

Note that in optimize command,

sum(x,2) == 1 constrains row sums to 1
sum(x,1) == 1 constrains column sums to 1
sum(sum(x.*A)) is the objective to be minimized
value(x) provides the optimal selection matrix
value(sum(sum(x.*A)))) provides the optimal score.

For your example

n = 3
A = [3 6 8;3 4 8;2 5 7]

value(x) is

 1     0     0

 0     1     0

 0     0     1

Optimal score is 14.

If you want to maximize the sum, you could just change the optimize command to optimize([sum(x,2) == 1, sum(x,1) == 1],-sum(sum(x.*A))) which minimizes the negative of the sum.

Here's a random 5 by 5 matrix:

0.8147    0.0975    0.1576    0.1419    0.6557
0.9058    0.2785    0.9706    0.4218    0.0357
0.1270    0.5469    0.9572    0.9157    0.8491
0.9134    0.9575    0.4854    0.7922    0.9340
0.6324    0.9649    0.8003    0.9595    0.6787

Optimal (producing minimum sum) x is

0 1 0 0 0

0 0 0 0 1

1 0 0 0 0

0 0 1 0 0

0 0 0 1 0

Optimal score is 1.7051.