Maximise sum of "non-overlapping" numbers from matrix

Question

Just looking for a bit of direction, I realise that the example given is possible to solve using brute force iteration, but I am looking for a more elegant (ie. mathematical?) solution which could potentially solve significantly larger examples (say 20x20 or 30x30). It is entirely possible that this cannot be done, and I have had very little success in coming up with an approach which does not rely on brute force...

I have a matrix (call it A) which is nxn. I wish to select a subset (call it B) of points from matrix A. The subset will consist of n elements, where one and only one element is taken from each row and from each column of A. The output should provide a solution (B) such that the sum of the elements that make up B is the maximum possible value, given these constraints (eg. 25 in the example below). If multiple instances of B are found (ie. different solutions which give the same maximum sum) the solution for B which has the largest minimum element should be selected.

B could also be a selection matrix which is nxn, but where only the n desired elements are non-zero.

For example: if A =

|5 4 3 2 1|
|4 3 2 1 5|
|3 2 1 5 4|
|2 1 5 4 3|
|1 5 4 3 2|

=> B would be

|5 5 5 5 5|

However, if A =

|5 4 3|
|4 3 2|
|3 2 1|

B =

|3 3 3|

As the minimum element of B is 3 which is larger than for

|5 3 1|

or

|4 4 1|

which also both sum to 9

Answer 1

Your problem is almost identical to the Assignment problem, which can e.g. be solved by the Hungarian algorithm in polynomial time.

Note that the assignment problem is usually a minimization problem, but multiplying your matrix with -1 and adding some constant should make the method applicable. Further, there is no formal tie-braking condition, for case of multiple optimal solutions. However, the method yields you a solution having the optimal sum. Let m be the minimum summand. Modify your matrix by setting all entries less or equal to m to zero and solve again. Either you get a solution with the same sum that is better than the last one. If not, the previous solution was already optimal.