首页   按字顺浏览 期刊浏览 卷期浏览 An Algorithm for the Knapsack Problem
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)



返 回