A dynamic programming algorithm for the Knapsack Problem with Setup |
| |
Affiliation: | 1. School of Business, Sun Yat-sen University, Guangzhou, China;2. School of Public Health, Sun Yat-sen University, Guangzhou, China;3. Department of Logisitics & Maritime Studies, The Hong Kong Polytechnic University, Hung Hom, Hong Kong |
| |
Abstract: | 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. |
| |
Keywords: | Knapsack problems Setup Dynamic programming Combination Production planning |
本文献已被 ScienceDirect 等数据库收录! |
|