It seems that there's no end to knapsack variations… here's the one I bumped into (at work):
- N items, each with the usual value and weight properties.
- M bins, each with an upper bound and a lower bound on the total weight of the items that can be assigned to it. (That is, the total weight of the items assigned to bin $j=1,\ldots,M$ should be at least $L_j$ and at most $U_j$, for some pre-defined $L_j, U_j$.)
But here comes the main problem:
- Each bin accepts only items from a specific (pre-defined) subset of the N items.
The task is to maximize the overall value with no need to use all the bins (due to the minimum weight).
What do you think ? Is this tractable ? How would you tackle/model and solve it (given the necessity of extracting the "ID"s of the items in each bin) ?
My knowledge in this specific field isn't enough… so, thanks in advance!