Is Dynamic 0/1 Knapsack a Total Joke?

Question

I have obtained a proof that would discredit a generally held idea regarding the 0/1 knapsack problem and I'm really having a hard time convincing my self I am right because I couldn't find any thing any where to support my claims, so I am going to first state my claims and then prove them and I would appreciate anyone to try to substantiate my claims further or disproof them. Any collaboration is appreciated.

Assertions:

1. The size of the bnb (branch and bound) algorithm for solving the knapsack problem is not independent of the K (capacity of the knapsack).
2. The size of bnb tree complete space is always of O(NK) with N being the number of items and not O(2^N)
3. The bnb algorithm is always better than the standard dynamic programming approach both in time and space.

Pre-assumptions: The bnb algorithm prone the invalid nodes (if the remaining capacity is less than the weight of current item, we are not going to extend it. Also, the bnb algorithm is done in a depth-first manner.

Sloppy Proof:

Here is the recursive formula for solving the knapsack problem:

Value(i,k) = max (Value(i-1,k) , Value(n-1 , k-weight(i)) + value(i)

however if k < weight(i): Value(i,k) = Value(i-1,k)

Now imagine this example:

K = 9
N = 3   
V W:   
5 4   
6 5   
3 2

Now here is the Dynamic solution and table for this problem:

Now imagine regardless of whether it is a good idea or not we want to do this using only the recursive formula through memoization and not with the table, with something like a map/dictionary or a simple array to store the visited cells. For solving this problem using memoization we should solve the denoted cells:

Now this is exactly like the tree we would obtain using the bnb approach:

and now for the sloppy proofs:

1. Memoization and bnb tree have the same amount of nodes
2. Memoization nodes is dependent of the table size
3. Table size is dependent of N and K
4. Therefore bnb is not independent of K
5. Memoization space is bounded by NK i.e. O(NK)
6. Therefore bnb tree complete space (or the space if we do the bnb in a breadth first manner) is always of O(NK) and not O(N^2) because the whole tree is not going to be constructed and it would be exactly like the momization.
7. Memoization has better space than the standard dynamic programming.
8. bnb has better space than the dynamic programming (even if done in breadth first)
9. The simple bnb without relaxation (and just eliminating the infeasible nodes) would have better time than memoization (memoization has to search in the look up table and even if the look up was negligible they would still be the same.)
10. If we disregard the look up search of memoization, it is better than dynamic.
11. Therefore bnb algorithm is always better than dynamic both in time and space.

Questions:

If by any mean my proofs are correct some questions would arise that are interesting:

1. Why bother with dynamic programming? In my experience the best thing you could do in dp knapsack is to have the last two columns and you can improve it further to one column if you fill it bottom to top, and it would have O(K) space but still can't (if the above assertions are correct) beat the bnb approach.
2. Can we still say bnb is better if we integrate it with relaxation pruning (with regard to time)?

ps: Sorry for the long long post!

Edit:

Since two of the answers are focused on memoization, I just want to clarify that I'm not focused on this at all! I just used memoization as a technique to prove my assertions. My main focus is Branch and Bound technique vs dynamic programming, here is a complete example of another problem, solved by bnb + relaxation (source: Coursera - Discrete Optimization) :

Answer 1

I think there is a misunderstanding from your side, that the dynamic programming is the state-of-the art solution for the knapsack problem. This algorithm is taught at universities because it is an easy and nice example for dynamic programming and pseudo-polynomial time algorithms.

I have no expertise in the field and don't know what is the state-of-the art now, but branch-and-bound approaches have been used for quite some time to solve the knapsack-problem: The book Knapsak-Problems by Martello and Toth is already pretty old but treats the branch-and-bound pretty extensively.

Still, this is a great observation from your side, that the branch and bound approach can be used for knapsack - alas, you were born too late to be the first to have this idea:)

There are some points in your proof which I don't understand and which need more explanation in my opinion:

1. You need memoization, otherwise your tree would have O(2^N) nodes (there will be obviously such a case otherwise knapsack would not be NP-hard). I don't see anything in your proof, that assures that the memoization memory/computation steps are less than O(NK).
2. Dynamical programming needs only O(K) memory-space, so I don't see why you could claim "bnb algorithm is always better than dynamic both in time and space".

Maybe your claims are true, but I'm not able to see it the way the proof goes now.

The other problem is the definition of "better". Is branch-and-bound approach better if it is better for most of the problems or the common problems or does it has to be better for the wost-case (which would not play any role in the real life)?

The book I have linked to has also some comparisons for the running times of the algorithms. The dynamic programming based algorithms (clearly more complex as the one taught at school) are even better for some kind of problems - see section 2.10.1. Not bad for a total joke!

Answer 2

First of all, since you are applying memorization, you are still doing DP. That's basically the definition of DP: recursion + memorization. And that is also good. Without memorization your computation costs would explode. Just imagine if two items both have weight 2 and a third and a fourth have weight 1. They all end up at the same node in the tree, you would have to do the computation multiple times and you'll end up with exponential running time.

The main difference is the order of computation. The way of computing the entire matrix is called "bottom-up DP", since you start with (0,0) and work yourself upwards. Your way (the tree approach) is called "top-down DP", since you start with the goal and work yourself down the tree. But they are both using dynamic programming.

Now to your questions:

You are overestimating how much you really save. N = 3 is a pretty small example. I quickly tried a bigger example, with N = 20, K=63 (which is still pretty small) and random values and random weights. This is the first picture that I've generated:

values: [4, 10, 9, 1, 1, 2, 1, 2, 6, 4, 8, 9, 8, 2, 8, 8, 4, 10, 2, 6]
weights: [6, 4, 1, 10, 1, 2, 9, 9, 1, 6, 2, 3, 10, 7, 2, 4, 10, 9, 8, 2]
111111111111111111111111111111111111111111111111111111111111111
111111111111111111111111111111111111111111111111111111111111111
111111111111111111111111111111111111111111111111111111111111111
111111111111111111111111111111111111111111111111111111111111111
111111111111111111111111111111111111111111111111111111111111111
111111111111111111111111111111111111111111111111111111111111111
111111111111111111111111111111111111111111111111111111111111111
111111111111111111111111111111111111111111111111111111111111111
111111111111111111111111111111111111111111111111111111111111111
011111111111111111111111111111111111111111111111111111111111101
000001011111111111111111111111111111111111111111111111111111101
000000010111111111111111111111111111111111111111111111111111101
000000000010101011111111111111111111111111111111111111111010101
000000000000000000001010101111111111111111111111111111111010101
000000000000000000000000000101010101111111111111111111101010101
000000000000000000000000000001010101011111111111111111101010101
000000000000000000000000000000000101000001111100001111100000101
000000000000000000000000000000000000000000010100000111100000101
000000000000000000000000000000000000000000000000000010100000101
000000000000000000000000000000000000000000000000000000000000101
000000000000000000000000000000000000000000000000000000000000001

This picture is a transposed version of your displayed matrix. Rows represent the i values (first i elements in the array), and the cols represent the k values (allowed weights). The 1s are the positions in the DP matrix that you will visit during your tree-approach. Of course you'll see a lot of 0s at the bottom of the matrix, but you will visit every position the the upper half. About 68% of the positions in the matrix are visited. A bottom-up DP solution will be faster in such a situation. Recursion calls are slower, since you have to allocate a new stack frame for each recursive call. A speedup of 2x with loops instead of recursive calls is not untypical, and this would already be enough to make the bottom up approach faster. And we haven't even talked about the memorization costs of the tree approach yet.

Notice, that I haven't used actual bnb here. I'm not quite sure how you would do the bound-part, since you actually only know the value of a node once you compute it by visiting its children.

With my input data, the bottom-up approach is clearly a winner. But that doesn't mean that your approach is bad. Quite the opposite. It can actually be quite good. It all depends on the input data. Let's just imagine that K = 10^18 and all your weights are about 10^16. The bottom-up approach would not even find enough memory to allocate the matrix, while your approach will succeed in no time.

However, you probably could improve your version by performing A* instead of bnb. You can estimate the best value for each node (i, k) with int(k / max(weight[1..i]) * min(values[1..i]) and prune a lot of nodes using this heuristic.

Answer 3

In practice dynamic programming can be better for integer 0/1 knapsack because:

1. No recursion means you can never run into a stack overflow
2. No need to do a lookup search for each node, so often faster
3. As you note, storing the last two columns means that the memory requirement is lower
4. The code is simpler (no need for a memoization table)