An improved heuristic for multidimensional 0-1 knapsack problems

For the multidimensional 0-1 knapsack problem a heuristic exists, based on Lagrange multipliers, that also enables the determination of an upper bound to the optimal criterion value. This heuristic is extended in two ways: (1) in each step, not one, but more multiplier values are computed simultaneously, and (2) at the end the upper bound is sharpened by changing some multiplier values. From a comparison using a large series of different test problems, the extensions appear to yield an improvement, on average, at the cost of only a modest amount of extra computing time.