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.

Improve this question
$\endgroup$
4
  • $\begingroup$ Does anything prevent putting every item in the infinite knapsack, whether or not it is in another knapsack? $\endgroup$
    – RobPratt
    Nov 20, 2019 at 13:06
  • 2
    $\begingroup$ Is this 3 questions disguised as one? $\endgroup$
    – SecretAgentMan
    Nov 20, 2019 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, 2019 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, 2019 at 15:25

1 Answer 1

Reset to default
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$
1
  • $\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, 2019 at 18:13

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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