An Algorithm for the Knapsack Problem
作者:
Umit Akinc,
期刊:
IIE Transactions
(Taylor Available online 1983)
卷期:
Volume 15,
issue 1
页码: 31-36
ISSN:0740-817X
年代: 1983
DOI:10.1080/05695558308974610
出版商: Taylor & Francis Group
数据来源: Taylor
摘要:
This paper presents an efficient algorithm for the general (as opposed to the binary) knapsack problem. The algorithm generates tight bounds on the variables from the LP relaxation of the problem which give the optimal values of most of the variables very quickly. A branch-and-bound procedure is then employed to solve the remaining reduced problem. Extensive computatonal tests have confirmed the efficiency of this approach for a wide variety of problems with as many as 5000 variables.
点击下载:
PDF (347KB)
返 回