کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
474602 | 699076 | 2015 | 11 صفحه PDF | دانلود رایگان |
![عکس صفحه اول مقاله: A dynamic programming algorithm for the Knapsack Problem with Setup A dynamic programming algorithm for the Knapsack Problem with Setup](/preview/png/474602.png)
• A conversion method of binary solution to an integer index is proposed for the KPS.
• A new storage reduction technique is used to improve a DP algorithm performance.
• Computational experiments show the efficiency of the proposed DP algorithm.
The Knapsack Problem with Setup (KPS) is a generalization of the classical Knapsack problem (KP), where items are divided into families. An individual item can be selected only if a setup is incurred for the family to which it belongs. This paper provides a dynamic programming (DP) algorithm for the KPS that produces optimal solutions in pseudo-polynomial time. In order to reduce the storage requirements of the algorithm, we adopt a new technique that consists in converting a KPS solution to an integer index. Computational experiments on randomly generated test problems show the efficiency of the DP algorithm compared to the ILOG׳s commercial product CPLEX 12.5.
Journal: Computers & Operations Research - Volume 64, December 2015, Pages 40–50