For an academic project, we are trying to solve the following problem.
Given $k$ and a matrix $M$ with $r$ rows and $c$ columns, we want to find a set $K$ of $k$ rows such that
$$\sum_{i=1}^c \min_{j \in K} M[j][i])$$
is minimal.
It can be seen that a (probably not so tight) upper bound for the complexity is $r \choose k$$ \cdot c$; it is my conjecture that the problem is NP-complete.
I have implemented some quick and dirty Branch and Bound algorithm, although it doesn't really scale to the numbers that I would like them to.. I would like to prevent incorporating greedy methods.
We tried to formulate this as a mixed integer programming problem, to take advantage of the smart heuristics that have been incorporated within that field, but the problem does not fit nicely (mostly due to the fact that we want to minimize the result of a set of min operators; this requires for each cell an additional integer variable + constraint).
As the problem formulation seems fundamental and elegant enough, I was wondering if other people have came across a similar problem? Are there scientific publications that describe the problem, heuristics or approximations to solve the problem?
Thanks in advance!