Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
474602 | Computers & Operations Research | 2015 | 11 Pages |
•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.