Exact algorithms for the Setup Knapsack problem

The Setup Knapsack problem consists in selecting items from a set of disjoint families of items, to enter a knapsack while maximizing its value. An item can be selected only if the knapsack is set up for items of its family. The authors give a 0-1 programming formulation and they propose a reformulation in which setup variables are replaced by equivalent Boolean unions of item assignment variables. The authors present a Dynamic Programming algorithm and two versions of a two-phase enumerative scheme. These algorithms solve this NP-hard problem to optimality in time that is at worst pseudo-polynomial. The authors test the algorithms on randomly generated test problems.