A dynamic programming algorithm for the Knapsack Problem with Setup

• 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.