I am trying to find some special structure of a type of multidimensional knapsack problem, in which all the capacities of dimensions are the same. so the capacity constraint can be formulated in a piecewise linear form. My question is that will this structure help solve MKP? Because I think it is well known it is much difficult to solve.

asked 19 Jun '13, 22:18

jc%20W's gravatar image

jc W
257
accept rate: 0%


What do you mean with "all the capacities of dimensions are the same"? Do you mean that entries of the resource vector b (in your knapsack constraints Ax <= b) are all the same real number?

In my experience MKPs are difficult to solve only if you insist on obtaining "exact" solutions. For most practical purposes you can set solver tolerances to 1-5% acceptable optimality gap, and commercial solvers will return such solutions basically instantly.

EDIT: the following is a fairly recent survey on methods to solve the knapsack and its variations, you may use it to get some initial reference if you intend to go deeper in this direction

http://pdf.aminer.org/000/226/090/the_quadratic_multiple_knapsack_problem_and_three_heuristic_approaches_to.pdf

despite the name of the file it is concerned with the quadratic version only marginally actually

link

answered 26 Jun '13, 06:25

Robin%20V's gravatar image

Robin V
112
accept rate: 0%

edited 26 Jun '13, 07:18

yes u r right i men every entry in vector b is the same.

Thx for the survey. I read that before. My question here is definitely on exact optimality. Of course in reality can try some metaheuristic to get good solutions (But i think that still depends on the scale like several hundred variables and less than 50 dimensions). But as I said, I am asking for some insight that how to utilize the feature or is there some structure I can use. For instance, will that help in doing reductions?

(26 Jun '13, 07:31) jc W
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
×7
×1

Asked: 19 Jun '13, 22:18

Seen: 2,476 times

Last updated: 26 Jun '13, 07:31

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