# A sum with a product-penalty

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:

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)

• So either you select all items and you can compute the penalty, or there is at least one item which is not selected and the penalty is $0$. Is that it? Dec 8, 2022 at 15:13
• Following up on the question from @fotanf, if $k < n$ the penalty term is automatically 0, right?
– prubin
Dec 8, 2022 at 16:34
• I guess the penalty product will be $\prod_{i=1}^k x_i \cdot b_i$ Dec 8, 2022 at 22:05
• Thanks for the comments. Having it in the previous version makes it indeed super easy and one can just sort the elements $a_i$ and set $x_i=1$ for all but the smallest. Now, it looks less intuative, but--if $x_i=0$ then the factor in the penalty $(1- x_i \cdot (1-b_i)) = 1$ and if $x_i=1$ then the factor is $(1- x_i \cdot (1-b_i)) = b_i$ (as I intended it to be). Dec 8, 2022 at 22:20

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.
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}