Let us consider the following optimization-problem: For a given set of tuples $T=(a_1,b_1),\dots,(a_n,b_n)$ and integers $k,C$. The task is to
\begin{align} \max \quad & \sum_{i=1}^n x_i \cdot a_i - C \cdot \prod_{i=1}^n (1 - x_i \cdot (1 - b_i)) \\ \text{subject to} \quad & \sum_{i=1}^n x_i \le k \\ \forall i=1,\dots,n \quad & x_i \text{ is binary} \end{align}
Note, when $x_i$ is not selected the factor $(1 - x_i \cdot (1 - b_i))$ in the penalty is $1$, and when $x_i$ is selected, then the factor is $b_i$.
I would like to know the name of this problem in literature and I am interested, whether it is NP-hard. As the problem seems to be quite fundamental, I am quite sure that I am not the first person to observe this problem. But I have not so many good ideas what that could be called like.
There is a strong connection to Knapsack and Subset-Sum. Thus, I have found somewhat similar but not close enough problems:
- The Product Knapsack: https://link.springer.com/content/pdf/10.1007/s11590-017-1227-5.pdf
- The Penalized Knapsack: https://www.sciencedirect.com/science/article/pii/S0167637705000751
However all relations to Knapsack result in the issue that in the presented problem, there are no weights to the tuples/elements.
The most desirable variant for me would be $a_i\in \mathbb Q_{\ge 0}, b_i\in \mathbb Q\cap[0,1)$, but I would also be happy with an idea for the case where $a_i$s and $b_i$s are integers (or anything else.
(Three months ago, I have asked this question in the StackExchange-Forum for CS-Theory. https://cstheory.stackexchange.com/questions/51832/complexity-of-a-sum-with-a-product)