Given a matrix $M = \left(a_{ij}\right)$ with non-negative integer entries, and a cost threshold $\alpha$, I want to find the maximum number of rows of $M$ I can select subject to a cost function $L$ not exceeding $\alpha$.
The cost function $L$ is pretty simple, you're given a vector of positive weights $v :=(\omega_1,\omega_2,\dots,\omega_n)$, and the cost is the dot product of $v$ with the maximum value in each of the selected rows. So for example, if $$ M = \begin{bmatrix} 1 & 2 & 0 & 0\\ 0 & 2 & 1 & 1\\ 0 & 0 & 2 & 0 \end{bmatrix} $$ and I selected the first two rows, then my cost for those two items would be $$ (\omega_1,\omega_2,\omega_3,\omega_4) \cdot (\max(1,0),\max(2,2),\max(0,1),\max(0,1)) = \omega_1+2\omega_2 + \omega_3+\omega_4. $$
The reason I've called this a knapsack problem variant is because giving each row a value of $1$, finding the maximal carrying capacity is the same as finding the maximum number of rows I can select. Unfortunately though, since the cost function is determined by the maximum, the cost of the items depends on the items already put into the knapsack, which makes this problem not well suited for dynamical programing.
I'll also note that a simple greedy approach, i.e. just picking the next row that has the lowest cost based on the rows already selected until you can't pick anymore rows is often much smaller than the true optimal solution even for small(ish) sized matrices.
Is there any known literature on this (or a similar) variant of the knapsack problem? Is this NP hard? If so, are there any methods I should explore for trying to find a good approximate solution?
Any thoughts or comments are greatly appreciated!
You can solve the problem via integer linear programming as follows. Let binary decision variable $x_i$ indicate whether row $i$ is selected. Let continuous decision variable $y_j$ represent $\max_{i: x_i = 1} a_{ij}$. The problem is to maximize $\sum_i x_i$ subject to linear constraints \begin{align} a_{ij} x_i &\le y_j &&\text{for all $i$ and $j$} \\ \sum_j \omega_j y_j &\le \alpha \end{align}