Optimization - maximizing the minimum of weighted contributions
I have a matrix. The limitation is to select only one item for each column. The row sums are then calculated using only the selected items. The goal is to maximize the minimum of row sums. Example:
matrix
1 2 3 4 → 4
2 2 2 2 → 2 + 2 = 4
3 1 1 3 → 3
So the minimum of the row sums of the selected items per column is min (4,4,3) = 3
How do you achieve this? I can't figure out anything other than brute force, which means we'll iterate over all the column permutations and their row sums. Seems to be such a simple task, what should be a more efficient way?
source to share
This problem is highly NP-hard by shorthand from 3-partition (prepare multiple duplicate three-partitioned input lines, one for each desired partition). A Mixed Integer Programming (MIP) solver is probably no better than brute force in the worst case, but it's easy enough to try. Suppose a
there are rows m
and columns in the matrix n
. In the following integer program, the variable 0-1 x(i,j)
is equal 1
if and only if an item a(i,j)
in the row i
and column is selected j
.
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}
source to share