Find the minimal subset of rows of some matrix such that the sum of each column over this rows exceeds some threshold

Question

Let $A$ be a an $n\times m$ real valued matrix. The problem is to find the minimal subset $I$ of rows (if there is any) such that the sum of each column $j$ over the corresponding rows exceeds some threshold $t_j$, i.e. $\sum_{i\in I}A[i,j]>t_j$ for all $j\in\{1,\dots m\}$.

Or, stated as optimization problem:

Let $A\in\mathbb{R}^{n\times m}, t\in\mathbb{R}^m$. Now solve \begin{align}\min_{\xi\in\{0,1\}^n}&\sum_{i=1}^n\xi_i\\\text{s.t.}&\,A^\top\xi>t\,.\end{align}

Actually, i would need a solution only for $m=2$, but the general might be interesting too.

Answer 1

The general $n \times m$ case is easily seen to be NP-hard by reduction from set cover. Add a column for each element; each row is the indicator function of a subset; set $t_j = 0$ for each column.

A slightly more complicated reduction from subset sum shows that this is NP-hard even for $m = 2$. Suppose we are given a subset sum problem instance where we have a set $B$ of integers and the goal is to find a subset of $B$ that sums to exactly $k$. We reduce this to your problem as follows: for each integer $b \in B$, add $[b, -b]$ as a row to $A$; then set $t_1 = k - 1$ and $t_2 = -k - 1$. This enforces that the sum of the chosen subset must be greater than or equal to $k$ and also less than or equal to $k$, and therefore exactly equal to $k$.

For solving this problem in practice, I would recommend an integer linear programming solver. Most such solvers have direct support for 0-1 variables, so the linear optimization version you describe in the question can be presented to the solver exactly as written.