4
$\begingroup$

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)

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

2 Answers 2

2
$\begingroup$

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.

$\endgroup$
2
$\begingroup$

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}

$\endgroup$
2
  • $\begingroup$ The transformation of the product into a sum is interesting. $\endgroup$
    – A.Omidi
    Dec 9, 2022 at 17:38
  • 1
    $\begingroup$ Thanks Abbas. My hat tip to maximum log-likehood method. $\endgroup$ Dec 9, 2022 at 17:46

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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