linear programming relaxed for MKP

问题:

how to calculate to find this relaxation. What should i know to find it. Suppose i have n items and m knapsack . So i wanted to know the number of m relaxation. Does anybody can give me some idea at least. I have been searching it for while. There is some article on internet but not much clear. Please at least someone say to me you should read this thing , you should know this thing e.i so i will very appreciate

Thank you

回答1:

I think your real question is "what is the exact definition of a Linear-Relaxed Knapsack Problem?", so I'm going to answer assuming it is.

The short answer is that a linear-relaxed KP is the fractionary version of a 0-1 KP [1].

Mathemathically, all you have to do is to convert the restriction "x_i belongs to the {0, 1} set" and convert it to "x_i must be any real number between 0 and 1", where x_i is the quantity of the i-th item in your solution backpack.

The name comes from the fact that the 0-1 KP is an integer programming problem. The 'linear' term means that the solution variables can assume continuous values.

Not all relaxations are linear, though. You might want to check out this Wikipedia page for them.

[1] http://en.wikipedia.org/wiki/Linear_programming_relaxation