6
$\begingroup$

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?

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

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

$\endgroup$
1
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – Mark L. Stone May 17 '15 at 1:00
  • $\begingroup$ 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. $\endgroup$ – Mark L. Stone May 17 '15 at 1:05

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.