PyTorch's new knapsack solver slashes peak RAM by 20x, handling 2000 items where the default crashes at 100
0/1 Knapsack Problem in PyTorch
PyTorch's default activation memory budget solver, dp_knapsack, builds a full 2D DP table of shape (items, max_weight), which becomes memory-prohibitive for large models. A new solver, dp_knapsack_sliding_hirschberg, combines a sliding window trick with Hirschberg's divide-and-conquer to reduce the table to just two rows, cutting peak RAM by 20x. On a 64GB machine, it handles 2000 items while the default crashes at 100, and runs about 37% faster. The author notes that if SciPy is acceptable, ilp_knapsack is even faster and exact.
with these two optimizations combined, we can decrease the DP table size from shape=(number of items, max weight) to shape=(2, max weight), effectively reducing a peak memory by a factor of 20x
- 7scan
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
- TacticalCoder
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?
- shoo
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. […]