I am trying to solve this model which is very similar to the original knapsack except the fact that if we take one item we should take exactly w_i copies of it. How should I solve it efficiently? If there is no way to get an exact solution are there approximate solutions with tight gaps? A copy of the model is here http://dl.dropbox.com/u/10279222/model.png Update: Can Lagrangian decomposition help in this case? asked 25 Apr '12, 06:29 Igor Pangal 
This is a variant of the multiple knapsack problem, with a side constraint of adding 0 or w_i of each type. The side constraint looks like a variation to the precedenceconstrained knapsack problem, since there are precedence constraints that impose relationships between the decision variables. answered 25 Apr '12, 16:02 lamclay 
A good IP solver should produce an exact solution for "reasonable" problem sizes ("reasonable size" being defined as a size the silver can handle :) ). I have two tactical suggestions. First, I would set branching priorities that would encourage the solver to branch on y before x. Second, the problem has a fair bit of symmetry. Specifically, permuting the j index produces a functionally equivalent solution (typical in packing problems). There are some interesting papers about algorithmic twists to exploit symmetry, but the easy way out is to constrain it away. Imposing lexicographic order on the columns of x will eliminate most of the symmetry. answered 26 Apr '12, 17:20 Paul Rubin ♦♦ 
To me, it looks like a (variant of) the "bounded multiple knapsack problem"; unfortunately those "have not yet been discussed in the literature, at least not to the knowledge of the authors of this paper."
answered 25 Apr '12, 09:10 fbahr ♦ 
if "original knapsack except the fact that if we take one item we should take exactly w_i copies of it" is really what you would like to do, then why not making a "pure" or "original" knapsack out of your problem by merging the w_i copies into one new item (which is w_i times bigger and w_i times more valuable) that can be packed or not?
answered 25 Apr '12, 09:48 Marco Luebbecke ♦ 1
Hm... maybe I was misreading the mathematical formulation: doesn't this ask to assign items of type i to (a fixed number of) "bins" j; each item of a particular type at most once per bin and exactly w_i times in total (or none); all "bins" with an uniform capacity of S?
(25 Apr '12, 09:58)
fbahr ♦
Florian, you are right. The model is a variant of a bin packing problem in the way you interpreted it.
(25 Apr '12, 10:02)
Marco Luebbecke ♦
