A sum with a product-penalty

Question

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)

Answer 1

You might consider using dynamic programming, as in the usual binary knapsack problem. Let $f(n,k,C)$ be the optimal objective value for the original problem. Conditioning on the value of $x_n\in\{0,1\}$ yields DP recursion $$f(n,k,C)=\max\left(f(n-1,k,C), a_n+f(n-1,k-1,C b_n)\right).$$ In the worst case, you will have $O(n k 2^n)$ states, but you could have fewer if the number of distinct values of $b_i$ is small.

Answer 2

One way is to replace the product part with its log. So if $z=\prod_i (1-x_i(1-b_i))$, this can be substituted with $\sum_i \log(1-x_i(1-b_i))$ or simply $\sum_i x_i \cdot \log b_i$.
This 2nd objective can form the lower level in bilevel or can be optimized independently with $\sum_{i}^n x_i \le k$ as constraint, then the optimal solution L used as constraint as below:
\begin{align}\max&\quad\sum_i a_i \cdot x_i\\\text{s.t.}&\quad L \le \sum_i x_i \cdot \log b_i\\&\quad\sum_{i}^n x_i \le k\end{align}