5
$\begingroup$

Consider $m$ knapsack and $n$ items. With each knapsack $j$ associated a capacity $c(j)$ and with each item $i$ associated a profit $p(i,j)$ (that depends on the knapsack, so it's not exactly the classic multiple knapsack problem) and a weight $w(i)$

  • There is a particular knapsack $j^*$ with infinite capacity and for which the following condition is satisfied : $$\forall i \in I, p(i,j^*) =0$$ We assume that this knapsack has already all the items (so there is a covering constraint that is always satisfied since the items are always there)

  • For a given knapsack $j$, an item $i$ can have a profit $p(i,j)$ that is either positive or negative.

  • An item $i$ must satisfy the following "presence" constraints:

    • Can be put in more than one finite knapsack (it can be "copied" and put in several knapsacks so it's not the classic generalized assignment problem).

    • Present at most once in the same knapsack.

The objective is to choose what items to pick in order to maximize the profit while satisfying the capacity constraint for each knapsack and the presence constraints for the items.

I'm interested in:

  1. Proving the complexity
  2. Finding upper-bounds: intuitively, is there a decomposition method that is suitable for this problem? If so, what is it?
  3. Finding lower-bounds: I was thinking about considering the knapsacks independently. Solving each one exactly by a DP and then assign the remaining items to the knapsack $j^*$. Do you have another heuristic?

PS: the number of items is $10000$ and the number of knapsacks is between $100$ and $500$ depending on the instance.

$\endgroup$
  • $\begingroup$ Does anything prevent putting every item in the infinite knapsack, whether or not it is in another knapsack? $\endgroup$ – RobPratt Nov 20 '19 at 13:06
  • 2
    $\begingroup$ Is this 3 questions disguised as one? $\endgroup$ – SecretAgentMan Nov 20 '19 at 13:18
  • $\begingroup$ @RobPratt I've edited the post. We can make the assumption that all of the items are already in the infinite knapsack and rule out the constraint on the presence at least once. Is that what are you thinking of ? $\endgroup$ – Joffrey L. Nov 20 '19 at 14:02
  • 1
    $\begingroup$ Yes, it seems that the infinite capacity knapsack can be eliminated. Also, what prevents solving exactly as independent knapsack problems? $\endgroup$ – RobPratt Nov 20 '19 at 15:25
4
$\begingroup$

It looks like there is no relationship between different knapsacks, so you can solve this exactly as $m$ independent 0-1 knapsack problems. Also, for knapsack $j$, you can eliminate any items $i$ that have $p(i,j)\le 0$.

| improve this answer | |
$\endgroup$
  • $\begingroup$ Actually there is some dependency that I am trying to understand. Also all this stuff is a heuristic of a problem that is explained here markus-beuckelmann.de/blog/google-hashcode-2017.html it's not the model itself. I would be grateful if you could check it $\endgroup$ – Joffrey L. Nov 20 '19 at 18:13

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.