How to find the "best vectors" in a given matrix whose sum of products is as small as possible? The input is a matrix $\mathbf{A}=[a_{ij}]$ of real numbers $a_{ij}&gt;0$ for all $i\in\{1,\ldots,k\}$ and $j\in\{1,\ldots,n\}$ and a real number $v$. The coefficient of the matrix are not all greater than $1$ nor all less than one.

The question is to find a subset $S$ of $\{1,\ldots,n\}$ and $S\neq \emptyset$ such that $$\sum_{i=1}^k\prod_{j\in S}a_{ij}\leqslant v.$$

In fact, in the optimization settings, I would like to find a subset $S$ whose sum of products is minimum. 

Example: Take $v=0.55$ and $$\mathbf{A}=\begin{bmatrix} 0.1&amp;2&amp;3\\2&amp;0.2&amp;0.1\end{bmatrix}.$$ This has the solution $S=\{1,3\}$. Its value (its sum of products) is $0.5$.

How to solve this problem?  Is this problem known (or is there any similar problem in the literature)?

Besides enumerating all subsets of $\{1,\ldots,n\}$, I cannot find a good way to solve the problem.
The problem is NP-complete.
I sketch a reduction from 3-SAT.

Consider Boolean variables $x_1,\ldots,x_n$ and clauses $c_1,\ldots,c_m$ over these variables, so that each clause consists of three literals.  The question is to decide whether there exists a truth setting of the variables so that every single clause is satisfied (and hence contains at least one true literal).

We construct a matrix with $n+m+1$ rows and $2n+1$ columns.


There is a special row $R^*$, and there is a special column $C^*$.
For every clause $c_j$, there is one corresponding row $R(c_j)$.
For every variable $x_i$, there is one corresponding row $R(x_i)$.
For every variale $x_i$, there are two corresponding columns $C^+(x_i)$ and $C^-(x_i)$.


Let $Z=100(m+n)^{100}$ be a huge integer.


The entry at the crossing of special column $C^*$ and special row $R^*$ is $1/Z^n$. All other entries in row $R^*$ take value $Z$. 
All entries at a crossing of $C^*$ with a clause row $R(c_j)$ are $Z$.
All entries at a crossing of $C^*$ with a variable row $R(x_i)$ are $1/Z$.
The crossings of variable row $R(x_i)$ with columns $C^+(x_i)$ and $C^-(x_i)$ take value $Z$; all remaining entries in row $R(x_i)$ are $1$.
If clause $c_j$ contains the positive literal $x_i$, then the crossing of row $R(c_j)$ and column $C^+(x_i)$ is $1/Z$; all other entries in row $R(c_j)$ are $1$.
If clause $c_j$ contains the negative literal $\lnot x_i$, then the crossing of row $R(c_j)$ and column $C^-(x_i)$ is $1/Z$; all other entries in row $R(c_j)$ are $1$.


It can be shown that the 3-SAT instance is satisfiable, if and only if the column selection problem has a solution $S$ for which the sum of products is at most $v=n+m+1$. Some comments:


The set $S$ must contain the special column $C^*$; otherwise the contribution of the special row $R^*$ to the objective function (sum of products) is at least $Z&gt;v$.
The set $S$ can contain at most one of the two columns $C^+(x_i)$ and $C^-(x_i)$; otherwise the contribution of row $R(x_i)$ to the objective function will be at least $(1/Z)\cdot Z\cdot Z&gt;v$.
For every clause $c_j$, the set $S$ must contain some column $C^+(x_i)$ and $C^-(x_i)$ so that the corresponding literal $x_i$ respectively $\lnot x_i$ satisfies $c_j$. Otherwise, the contribution of row $R(c_j)$ to the objective function will be at least $Z&gt;v$.