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:
- Proving the complexity
- Finding upper-bounds: intuitively, is there a decomposition method that is suitable for this problem? If so, what is it?
- 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.