# Finding minimum from matrix

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?

• Are you looking for an algorithm? – Ward Beullens May 16 '15 at 14:33
• @WardBeullens Yes – user4904589 May 16 '15 at 14:40

## 2 Answers

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

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.

• If you get up to a matrix size of several thousand by several thousand, or this must run in a time-constrained real-time environment, you may wish to go with a more computationally efficient approach. For small problems, say matrix no more than 1000 by 1000, it solves in a flash just as is. You can solve this as a continuous rather than binary LInear Program, by adding constraint 0 <= x <= 1, and it solves faster, you just have to make sure your solver provides an integer (binary) optimal solution, which does exist - so stick with Simplex, not Interior Point, unless you use crossover step. – Mark L. Stone May 17 '15 at 1:00
• Declare x = sdpvar(n,n,'full') in YALMIP instead of x = binvar(n,n,'full') and add the constraint 0 <= x <= 1 in order to solve it as a continuous Linear Programming problem. And the fastest executing approach will be a specialized linear assignment optimization algorithm. – Mark L. Stone May 17 '15 at 1:05