1
$\begingroup$

The input is a matrix $\mathbf{A}=[a_{ij}]$ of real numbers $a_{ij}>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&2&3\\2&0.2&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.

$\endgroup$
2
$\begingroup$

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>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>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>v$.
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.