Nonlinear Knapsack with small integer weights

Question

I have a problem that looks like a 0-1 Knapsack problem, except that the value of each item is a vector of length about 5, $v=(v_1,\dots,v_5)$. I want to maximize the product of components of the sum of the value vectors that are selected. In other words, if $S$ is the set of value vectors for the selected items, I want to maximize $$\prod_{i=1}^5 \sum_{v \in S} v_i.$$

I know that there is a dynamic programming algorithm for that would be very fast for a normal Knapsack with my parameters (max weight 100, about 100 different items) but it isn't directly applicable to my problem, as in my case an optimal weight $w$ solution doesn't help find a weight $w+1$ solution.

Does a fast general algorithm for my problem exist? If not, could I preprocess the vectors in some slow way to make this fast? They are often nonzero in only one component.

Answer 1

There is an efficient algorithm for the special case where all value vectors have only a single non-zero coordinate, and where all items have weight 1.

Let $S_j$ denote the set of value vectors that are nonzero only in the $j$th coordinate. Sort them by decreasing value. Let $t_{j,w}$ denote the sum of the $j$th coordinates of the $w$ largest vectors in $S_j$. Then your problem becomes to find $w=(w_1,\dots,w_5)$ such that

$$t_{1,w_1} \times \cdots \times t_{5,w_5}$$

is maximized, subject to $w_1+\dots+w_5 \le 100$. This can be solved using dynamic programming, with fewer than $5 \times 100^2$ steps of computation. In particular, for each $j,w$, we compute the maximum possible value of $t_{1,w_1} \times \dots \times t_{j,w_j}$ subject to $w_1+\dots+w_j \le w$. This can be done efficiently using dynamic programming, by solving the subproblems in order of increasing $j$. The solution for $j=5$ and $w=100$ then gives a solution to your original problem.

What if a few of the items have more than one non-zero coordinate? One approach would be to enumerate over all possible subsets of those vectors, then for each, identify which of the remaining vectors to pick using the above algorithm. If you have 10 items with more than one non-zero coordinate, this might require something like $2^{10} \times 5 \times 100^2$ steps of computation (probably fewer in practice). Perhaps someone else will find a better way to handle this case.