Hi guys,
I am studying about Knapsack problem. So i do not understand one thing here.
the profit/pseudo-resource consumption ratios Uj=Pj/Wj with Wj=Rji*Aj;
I hope so you people know this equation thus i think no need more explanation.
I wanted to calculate Aj here. What is that LP relaxation . How they are calculating using total capacity and weight (size of item). If i have n item and m capacity it means i should to have m LP relaxation variable. Is it right ?
Some one saying like
One of the simplest methods to obtain reasonably good multipliers is to solve the linear programming (LP) relaxed MKP in which the variables xj may get arbitrary values from the interval [0, 1] and to use the values of the dual variables as the surrogate multipliers. In other words,aj is set to the shadow price of the j-th constraint in the LP relaxed MKP.
How they are calculating shadow price of j th constraint in the LP relaxed MKP. I am searching from Google bro for while but there is not so much clear . Does anyone know to understand by easy way ? Thank you to read until here :)