Another relaxation is the following one: take again the same problem and u are the optimal dual of the relaxed problem. What we do here is transform all of the constraints into one constraint where the multipliers are the optimal duels of the relaxed problem. This is called surrogate relaxation. And again this is a knapsack problem. In some cases this relaxation is better than the Lagrangean relaxation.