Linear programming weakened for MKP

Question

how to calculate to find this relaxation. What I need to know to find it. Suppose I have n items and an m backpack. So I wanted to know the amount of relaxation. Someone can give me at least some idea. I have been looking for him so far. There is an article on the Internet, but not very clear. Please at least someone will tell me that you should read this thing, you should know this thing ei, so I will be very grateful

thanks

Answer 1

I think your real question is: “What is the exact definition of the problem with a linear relaxation backpack?”, So I'm going to answer, suggesting that it is.

The short answer is that linearly relaxed KP is a fractional version of 0-1 KP [1] .

Mathematically, all you have to do is convert the constraint "x_i belongs to the set {0, 1}" and convert it to "x_i should be any real number from 0 to 1", where x_i is the number of the ith element in your backpack solutions.

The name comes from the fact that 0-1 KP is an integer programming task. A “linear” term means that decision variables can take on continuous values.

However, not all relaxations are linear. You can check this Wikipedia page for them.

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