Optimal solution to a table of numbers

Question

I want to maximise the score of the following table, choosing one item from each column/row, so no two items are on the same row or column. Score to maximise is just adding all the choices together.

$$*\quad A\quad B\quad C\quad D\quad E$$ $$\alpha\quad 16\quad 16\quad 18\quad 18\quad 18$$ $$\beta\quad 20\quad 18\quad 16\quad 12\quad 10$$ $$\gamma\quad 20\quad 18\quad 18\quad 16\quad 16$$ $$\delta\quad 18\quad 18\quad 16\quad 16\quad 8$$ $$\epsilon\quad 10\quad 12\quad 14\quad 14\quad 14$$

Example: ($^{C}$ means chosen)

$$*\quad A\quad B\quad C\quad D\quad E$$ $$\alpha\quad 16^{C}\quad 16\quad 18\quad 18\quad 18$$ $$\beta\quad 20\quad 18\quad 16\quad 12\quad 10^{C}$$ $$\gamma\quad 20\quad 18^{C}\quad 18\quad 16\quad 16$$ $$\delta\quad 18\quad 18\quad 16^{C}\quad 16\quad 8$$ $$\epsilon\quad 10\quad 12\quad 14\quad 14^{C}\quad 14$$

Gives a score of $16+10+18+16+14=74$

Now there are a few ways to do this, but can firstly, someone actually tell me if $88$ really is the best result and how can this be done computational. Note: I am a Mathematics student and would normally approach such a problem with graph theory, but would like to see computation methods.

Answer 1

This is called an assignment problem. The most common algorithm to solve it is known as the Hungarian algorithm, and runs in $O(n^3)$ time.

Another interesting observation is that it corresponds to computing the permanent of a matrix in the tropical (max-plus) semiring. Unfortunately, though, a Google search for "tropical permanent" is complicated by the non-mathematical meanings of these words.

Answer 2

This can be formulated as a linear programming problem. Since you want to choose the right positions on each line and column, you may formulate this as finding a matrix $X$ with entries zero and $1$ such that the sum on each line and column is equal to $1$ and the dot product between $A$ and $X$ is maximized.

Since we want to maximize a linear functional with linear constraints and we expect the variables to take values in $\{0,1\}$ we may relax this to allow variables to belong to $[0,1]$. This is because linear functions always attain their extremal values at the vertices of the computational domain. That's why the simplex algorithm works in this case.

The complexity of the simplex algorithm is not polynomial, apparently, but for small examples it works really well.

Here's a Matlab implementation using linprog and the simplex algorithm:

function sci_comp1_mat

A = [16 16 18 18 18; 
     20 18 16 12 10;
     20 18 18 16 16;
     18 18 16 16 8;
     10 12 14 14 14];

n = size(A,1);
f = double(A(:)); % coeffs matrix
% constraints
% sum on lines

C = zeros(2*n,n^2);
for i=1:n
   C(i,linspace((i-1)*n+1,i*n,n))=1;
   C(n+i,linspace(i,n^2-n+i,n))=1;
end
b = ones(2*n,1);

lb = zeros(size(f));
ub = ones(size(f));

options.Algorithm = 'simplex';
x = linprog(-f,C,b,[],[],lb,ub,[],options);
dot(x,f)
x = reshape(x,n,n);
round(x)


Res = A.*x

Res(Res==0) = '';
Res(:)

Answer 3

I agree 88 looks like the best score.

You might use a tree. The root node contains 5 subnodes (16 16 18 18 18), each of them contains 4 subnodes (excludes the column of the parent node), etc.

Traverse the tree recursively and search for the highest score (breadth first or depth first). I wouldn't actually build the tree, just pretend it's there and look up the cell values when you need to compare them. The recursive function would be passed a row index and current score then call itself for each of the 1-5 subnodes.

This has O(N!) complexity so it doesn't scale.

It sounds tricky to find the highest score without an exhaustive search like this. If you only want a reasonably good guess, then you could ignore the branches with the lowest scores at each level.

Answer 4

I couldn't resist to try out the Hungarian method to prove that 88 is the maximal value that could be achieved. I found a description here: Bruff, Derek, "The Assignment Problem and the Hungarian Method", without any explanation why the method terminates an what is its running time. The algorithm transforms a cost matrix of an assignment problem to a new cost matrix by adding numbers to rows or columns of a cost matrix. A theorem from the document says "If a number is added to or subtracted from all of the entries of any one row or column of a cost matrix, then an optimal assignment for the resulting cost matrix is also an optimal assignment for the original cost matrix".

This is because a number $a$ is added to all entries of a row or a column then the value of any assignment is increased by $a$.

The method described in the document finds a minimum. To find maximum we multiply the cost matrix by $-1$ and find a minimum of this matrix,

So we start with

  16  16  18  18  18
  20  18  16  12  10
  20  18  18  16  16
  18  18  16  16   8
  10  12  14  14  14

and multiply it by $-1$

 -16 -16 -18 -18 -18
 -20 -18 -16 -12 -10
 -20 -18 -18 -16 -16
 -18 -18 -16 -16  -8
 -10 -12 -14 -14 -14

To avoid negative numbers we add $20$ to each element. hen for each row we subtract its minimum.

   4   4   2   2   2   | -2
   0   2   4   8  10   |
   0   2   2   4   4   |
   2   2   4   4  12   | -2
  10   8   6   6   6   | -6

   2   2   0   0   0
   0   2   4   8  10
   0   2   2   4   4
   0   0   2   2  10
   4   2   0   0   0

Now for each row the minimum should be subtracted but this is 0 for every row so there is nothing to do.

The following matrix can be ignored if you haven't read the linked document.

   +----------------
   |   2   4   8  10
   |   2   2   4   4
   +----------------
   +----------------

We continue to transform the matrix:

   2   2   0   0   0   |
   0   2   4   8  10   | -2
   0   2   2   4   4   | -2
   0   0   2   2  10   |
   4   2   0   0   0   |
  ------------------
  +2

and finally, arrive at

   4   2   0   0   0
   0   0   2   6   8
   0   0   0   2   2
   2   0   2   2  10
   6   2   0   0   0

Now we select the following positions containing 0 and mark them by x

   4   2   0   x  0
   x   0   2   6   8
   0   0   x   2   2
   2   x   2   2  10
   6   2   0   0   x

These x-positions show an admissible assignment in this cost matrix, and it is minimal because a value smaller than 0 cannot be achieved.

This assignement is also optimal for the initial cost matrix. TSo we have proven that

18+20+18+18+14=88

is the maximum value.