An Improved Heuristic for Multidimensional 0-1 Knapsack Problems
作者:
VolgenantA.,
ZoonJ. A.,
期刊:
Journal of the Operational Research Society
(Taylor Available online 1990)
卷期:
Volume 41,
issue 10
页码: 963-970
ISSN:0160-5682
年代: 1990
DOI:10.1057/jors.1990.148
出版商: Taylor&Francis
关键词: heuristics;integer programming;knapsack problem;lagrange multipliers;upper bounds
数据来源: Taylor
摘要:
AbstractFor 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.
点击下载:
PDF (3258KB)
返 回