.png){kind=icon}
返回
A cross entropy algorithm for the Knapsack problem with setups
.png){kind=icon}
PRE
AI
DOI：10.1016/j.cor.2006.02.028.png)
.png){kind=icon}
原文求助.png){kind=icon}
分享.png){kind=icon}
收藏
摘要
En 中文
In this article We propose a new metaheuristic-based algorithm for the Integer Knapsack Problem with Setups. This problem is a generalization of the standard Integer Knapsack Problem, complicated by the presence of setup costs in the objective function as well as in the constraints. We propose a cross entropy based algorithm, where the metaheuristic scheme allows to relax the original problem to a series of well chosen standard Knapsack problems, solved through a dynamic programming algorithm. To increase the computational effectiveness of the proposed algorithm, we use a turnpike theorem, which sensibly reduces the number of iterations of the dynamic algorithm. Finally, to testify the robustness of the proposed scheme, we present extensive computational results. First, we illustrate the step-by-step behavior of the algorithm on a smaller, yet difficult, problem. Subsequently, to test the solution quality of the algorithm, we compare the results obtained on very large scale instances with the output of a branch and bound scheme. We conclude that the proposed algorithm is effective in terms of solution quality as well as computational time. (C) 2006 Elsevier Ltd. All rights reserved.
Keyword:
combinatorial optimization
metaheuristics
Knapsack problem
scheduling
dynamic programming
cross entropy
AI总结
对已上传原文的论文进行重点信息的提取，主要内容包括：简要概述、研究摘要、背景介绍、关键亮点、图文解析、展望与总结。
期刊
C
IF:
4.3
论文数:
6.5K
被引数:
1.8W
机构
暂无机构信息
引用论文
Growth and annihilation of microwave-induced free radicals in rice starch微波诱导自由基在稻米淀粉中的生成与湮灭.png)
IF0
PREAI
分享收藏分享收藏
查看更多内容