2
$\begingroup$

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.

$\endgroup$
5
  • 1
    $\begingroup$ What time are you aiming for? If by max weight you mean the maximum possible value obtainable for each of the coordinates, then DP algorithm can be naturally extended for your problem with running time $100^6$ operations $\approx 0.5-5$ hours (for each of $100^5$ possible vectors, you need to determine whether you can get this vector using first $i$ items). It'll probably be much faster if implemented in a top-down fashion (since many vectors are probably unachievable). $\endgroup$
    – Dmitry
    Nov 2, 2021 at 18:58
  • $\begingroup$ I'm looking to solve this on millions of different subsets of about 300 or so items. Actually, that could be a key to solving it efficiently! There will be a lot of overlap between the partial solutions. $\endgroup$
    – Joonazan
    Nov 3, 2021 at 0:37
  • $\begingroup$ I'm going to try to do a divide and conquer version of the DP approach directly on the original problem rather than on this version, though. $\endgroup$
    – Joonazan
    Nov 3, 2021 at 0:41
  • $\begingroup$ Are the components of the value vectors usually small integers, or might they be large numbers? $\endgroup$
    – D.W.
    Nov 3, 2021 at 17:51
  • $\begingroup$ Does every item have weight 1, or do the weights vary? Are the weights positive integers? $\endgroup$
    – D.W.
    Nov 3, 2021 at 22:58

1 Answer 1

0
$\begingroup$

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.

$\endgroup$
1
  • $\begingroup$ This one component at a time approach seems really good! Much cheaper than finding pareto fronts. $\endgroup$
    – Joonazan
    Nov 5, 2021 at 13:53

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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