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

alt text

Update: Can Lagrangian decomposition help in this case?

asked 25 Apr '12, 06:29

Igor%20Pangal's gravatar image

Igor Pangal
147210
accept rate: 0%

edited 25 Apr '12, 14:32


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 precedence-constrained knapsack problem, since there are precedence constraints that impose relationships between the decision variables.

link

answered 25 Apr '12, 16:02

lamclay's gravatar image

lamclay
1314
accept rate: 0%

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.

link

answered 26 Apr '12, 17:20

Paul%20Rubin's gravatar image

Paul Rubin ♦♦
14.6k412
accept rate: 19%

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."

Edit: Quite obviously, I missed some important things: the "global" constraint of exactly w_i items (or none) doesn't seem to be easily transformable to the BMKP "framework" (if at all) - and the "at most once per bin" requirement makes it rather a variant of the (easier to solve?) 0-1 MPK.

Well, probably I should leave this question open to someone who really knows what (s)he's talking about.

link

answered 25 Apr '12, 09:10

fbahr's gravatar image

fbahr ♦
4.6k716
accept rate: 13%

edited 26 Apr '12, 12:46

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?

edit taking Florian's comment into account, I see that this is not what your model describes.

link

answered 25 Apr '12, 09:48

Marco%20Luebbecke's gravatar image

Marco Luebbecke ♦
3.4k1615
accept rate: 16%

edited 25 Apr '12, 10:03

1

Hm... maybe I was mis-reading 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 ♦
Your answer
toggle preview

Follow this question

By Email:

Once you sign in you will be able to subscribe for any updates here

By RSS:

Answers

Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text](http://url.com/ "Title")
  • image?![alt text](/path/img.jpg "Title")
  • numbered list: 1. Foo 2. Bar
  • to add a line break simply add two spaces to where you would like the new line to be.
  • basic HTML tags are also supported

Tags:

×13

Asked: 25 Apr '12, 06:29

Seen: 1,839 times

Last updated: 26 Apr '12, 17:20

OR-Exchange! Your site for questions, answers, and announcements about operations research.