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.