首页   按字顺浏览 期刊浏览 卷期浏览 A hard knapsack problem
A hard knapsack problem

 

作者: Chia‐Shin Chung,   Ming S. Hung,   Walter O. Rom,  

 

期刊: Naval Research Logistics (NRL)  （WILEY Available online 1988）
卷期: Volume 35, issue 1  

页码: 85-98

 

ISSN:0894-069X

 

年代: 1988

 

DOI:10.1002/1520-6750(198802)35:1<85::AID-NAV3220350108>3.0.CO;2-D

 

出版商: Wiley Subscription Services, Inc., A Wiley Company

 

数据来源: WILEY

 

摘要:

AbstractIn this article we develop a class of general knapsack problems which are hard for branch and bound algorithms. The number of alternate optimal solutions for these problems grows exponentially with problem parameters. In addition the LP bound is shown to be ineffective. Computational tests indicate that these problems are truly difficult for even very small problems. Implications for the testing of algorithms using randomly generated problems is discussed.

 

点击下载:  PDF (660KB)



返 回