.png){kind=icon}
返回
A Lagrangean based solution algorithm for the multiple knapsack problem with setups
.png){kind=icon}
PRE
AI
DOI：10.1016/j.cie.2020.107089.png)
.png){kind=icon}
原文求助.png){kind=icon}
分享.png){kind=icon}
收藏
摘要
En 中文
We consider the multiple knapsack problem with setups which is a generalization of the classical knapsack problem. In this problem, there are multiple knapsacks and the items belong to families such that an item can be placed in a knapsack only if its family is selected and assigned to that knapsack. We present an algorithm based on a Lagrangean relaxation of the problem that takes advantage of the structure of the problem. The algorithm produces solutions whose quality can be assessed automatically without ever knowing the optimal solutions. We carry out a computational study to evaluate the performance of the proposed algorithm on a benchmark data set from the literature. The results show a great performance of the algorithm compared to published state-of-the-art approaches, as it generates better values for 9% of the instances and the same values for 90% of the instances. The algorithm generated new best-known values for 6% of the instances compared to both the published state-of-the-art approaches and the commercial solver CPLEX. We also report the results of an additional computational study that show that the algorithm scales up extremely well, solving near-optimally very large instances with up to 5 knapsacks, 200 families, and 300,000 items in a reasonable amount of time on a desktop PC.
Keyword:
Integer programming
Multiple knapsack problem with setups
Lagrangean relaxation
AI总结
对已上传原文的论文进行重点信息的提取，主要内容包括：简要概述、研究摘要、背景介绍、关键亮点、图文解析、展望与总结。
期刊
IF:
6.5
论文数:
1.0W
被引数:
3.8W
机构
引用论文
.png){kind=icon}
分享收藏
分享收藏分享收藏
查看更多内容