Complexity of a knapsack variant

Question

Consider the following traditional integer knapsack problem:

$\max \sum_{i=1}^k p_i \cdot x_i\\ \text{s.t.} \sum_{i=1}^k w_i \cdot x_i \leq W \\ x_i \in \{0,\ldots,k_i\} \text{ for each } i$

Now consider a laminar family $\mathcal{I}$ of sets, i.e., a collection of subsets of $\{1,\ldots,k\}$ such that for each pair $I_1,I_2 \in \mathcal{I}$ it either holds that $I_1 \subseteq I_2$ or $I_1 \supseteq I_2$ or $I_1 \cap I_2 = \emptyset$. For each of these subsets $I_j \in \mathcal{I}$, we insert an additional cardinality constraint of the form

$\sum_{i \in I_j} x_i \leq \mu_j$

for some number $\mu_j$.

Clearly, this problem is weakly $NP$-complete in general since it contains the traditional (integer) knapsack problem. The question is what happens if the profits $p_i$ are polynomially bounded. Does the problem remain $NP$-complete or is it easy to solve now? We are thinking about this problem for months now.

What we know so far:

• If we omit the cardinality constraints or restrict ourselves to only one cardinality constraint that involves each of the variables, the problem becomes easy to solve (this isn't as trivial as it sounds since the maximum amounts $k_i$ are still not polynomially bounded).
• Accordingly, if the maximum amounts $k_i$ are polynomially bounded, the problem becomes easy to solve as well.

The above results imply that, in order to prove $NP$-completeness, a possible reduction would need to make use of decision variables that are not polynomially bounded and must incorporate suitable laminar cardinality constraints with values $\mu_j$ that aren't polynomially bounded as well.

So, does anyone have some clue on how to prove or disprove the $NP$-completeness of the problem?

Answer 1

It can be solved by a similar DP for traditional knapsack problem, and thus still weak NP-complete. In the following we assume that the subsets $I_j$ are mutually disjoint, and the other case (some subsets are super sets of others) is similar.

In the DP algorithm for knapsack, let $T[p,i]$ be the minimum weight to reach profit $p$ by only using the first $i$ items. Now arrange the items such that all items in the same $I_j$ are consecutive. Since $I_j$ are disjoint, when dealing with $x_i$, we only need to consider how many items in $I_j$ can be picked. Thus, for each $p$ and $i$, let $D[p,i,q]$ be the minimum weight to reach profit $p$ by only using the first $i$ items and using only $q$ items in $I_j$. The table size is bounded by $P\times n^2$, where $n$ is the number of items and $P$ is the maximum profit. Since you assume that $P$ is polynomial, it takes polynomial time.