4

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)

xtyner
  • 41
  • 2
  • 3
    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? – fontanf Dec 08 '22 at 15:13
  • 1
    Following up on the question from @fotanf, if $k < n$ the penalty term is automatically 0, right? – prubin Dec 08 '22 at 16:34
  • I guess the penalty product will be $\prod_{i=1}^k x_i \cdot b_i$ – Sutanu Majumdar Dec 08 '22 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). – xtyner Dec 08 '22 at 22:20

2 Answers2

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}

ə̷̶̸͇̘̜́̍͗̂̄︣͟
  • 5,412
  • 5
  • 22
  • 55
Sutanu Majumdar
  • 3,461
  • 1
  • 2
  • 11
2

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.

RobPratt
  • 32,006
  • 1
  • 44
  • 84