It seems that there's no end to knapsack variations… here's the one I bumped into (at work):

There are:

  • 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!

  • $\begingroup$ Yes, exactly :) $\endgroup$
    – dezzeus
    Dec 14 '18 at 14:45
  • $\begingroup$ What do you mean by "with no need to use all the bins"? If all the lower bounds on the bins are positive then, from the way you describe the problem, you are forced to use all the bins. $\endgroup$
    – Vincenzo
    Dec 14 '18 at 14:53
  • $\begingroup$ It was just to reiterate that if the available items weren't enough to exceed the minimum weight for one of the bins, that bin can be left empty. $\endgroup$
    – dezzeus
    Dec 14 '18 at 14:58
  • $\begingroup$ But then, you don't really have that as a constraint; in this case you should remove the minimum weight requirement from the description. $\endgroup$
    – Vincenzo
    Dec 14 '18 at 15:01
  • $\begingroup$ Sorry, I don't get your point… I just tried to describe the problem, but if some details doesn't count, then don't count them (but please motivate it) :) $\endgroup$
    – dezzeus
    Dec 14 '18 at 15:04

Your Answer

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

Browse other questions tagged or ask your own question.