I have a matrix. The constraint is to choose only one element per column. The row sums are then calculated using only the chosen elements. The objective is to maximize the minimum of the row sums. Example:
matrix
1 2 3 4 -> 4
2 2 2 2 -> 2+2 = 4
3 1 1 3 -> 3
Thus the minimum of row sums of the chosen elements per column is min(4,4,3) = 3
How to achieve this? I cannot figure out anything else than brute force, which means going through all the column permutations and their row sums. It seems such a simple task that there should be a more efficient way?
This problem is strongly NP-hard by reduction from 3-partition (prepare several duplicate rows consisting of the 3-partition input, one for each desired partition). A mixed-integer programming (MIP) solver likely is not better than brute force in the worst case, but it's easy enough to be worth a try. Suppose that the matrix a has m rows and n columns. In the following integer program, the 0-1 variable x(i,j) is 1 if and only if the element a(i,j) at row i and column j is chosen.
maximize z
subject to
for all i in [1, m], -z + sum for j in [1, n] of a(i,j) x(i,j) >= 0
for all j in [1, n], sum for i in [1, m] of x(i,j) = 1 (or is it <= 1?)
for all i in [1, m], for all j in [1, n], x(i,j) in {0, 1}