.png){kind=icon}
.png){kind=icon}
Return
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}
Original request for help.png){kind=icon}
Share.png){kind=icon}
Save
Abstract
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.
Keywords:
combinatorial optimization
metaheuristics
Knapsack problem
scheduling
dynamic programming
cross entropy
AI Summary
Key information extracted from the uploaded paper, including a brief overview, abstract, background, key highlights, visual analysis, and future outlook.
Journal
C
IF:
4.3
Papers:
6.5K
Citations:
1.8W
Organization
No organization information available