0/1 Knapsack Problem in PyTorch

In practice one should almost always use the "combo" algorithm to solve 0-1 knapsack problems. It will likely be orders of magnitude faster than any of these approaches (for medium-large instances, at least). There's code and references here: https://hjemmesider.diku.dk/~pisinger/codes.html

0/1 Knapsack is a wonderful little problem, especially with its dynamic programming solution.

Now I may be mistaken but when I learned about 0/1 Knapsack three decades ago, my immediate thought was that for quite some cases you could do, using dynamic programming, an approximate version (requiring less memory and hence well, for example fitting into memory) and prove that your solution was "at most 1% off of the optimal solution". Never really looked into it though so I may have be wrong.

Basically say you need to 0/1 Knapsack the quantities 1739, 2989, 3798 and 4233, etc.: you can e.g. divide them by 10 and then round them up, so you've now got 174, 299, 380 and 424 and you need much less memory to run your dynamic programming solution to 0/1 Knapsack. And the best solution you find is guaranteed to be at most x% off the optimal solution.

Something like that. Does that work? Anyone ever heard about something similar?

I was curious about the issue the author called out with the baseline knapsack algorithm -- that it was running out of memory.

It looks like pytorch's various knapsack implementations (including the one contributed by the author) are here:

https://github.com/pytorch/pytorch/blob/31ba9a56657bc887c957...

appears to be used e.g. here

https://github.com/pytorch/pytorch/blob/31ba9a56657bc887c957...

One thing that jumps out at me while staring at the baseline dp_knapsack code is that it isn't very clear what the units used to measure memory are meant to be. The dp_knapsack code assumes that memory & max_memory (aka the memory budget) are floats. dp_knapsack internally multiplies these floating-point memory values by 10,000 & then rounds them to integers to quantise the memory values -- the quantised max_memory value defines the size of one dimension of the dynamic programming table. the other dimension is sized by the item count.

From reading patches of partitioners.py, it seems like the memory budget is meant to be a floating point number between 0.0 & 1.0, and presumably the memory of each item is normalised relative to that memory budget?

If so, & dp_knapsack is called with a max_memory of 1.0, then the a 2d array for n items is allocated and m=10,000 quantised memory values is allocated as shape (n+1, m+1). So for 100 items that'd be an array of shape (101, 10001) - it's filled with float32s, so 4 bytes per element, so the size required for the table would be ... about 4MB.

So it's not obvious why that would be running out of memory.

Another possible explanation of why the baseline dp knapsack could be using a bunch of memory -- speculation -- is that some code could be calling dp_knapsack with a different unit convention than what dp_knapsack expects --- suppose a caller passes in memory & max_memory values that are measured in floating-point GB. If the max_memory was passed in as 1024.0 then, for 100 items, the dp_knapsack code would allocate a float32 array of shape (101, 10240001) and this would require about 4GB.

Given the units of these inputs aren't documented (& certainly not enforced by the type system) & there aren't runtime range checks on the value of max_memory there's a lot of room for something like this to be happening.

Perhaps dp_knapsack could be reimplemented where it is responsible for rescaling input memory values relative to max_memory, where the rescaling always forces max_memory to be 1 before the memory values are quantised. Then there wouldn't be a way for the caller to get the undocumented calling convention wrong.