A Unified Exact Approach for Knapsack Problems with Side Constraints

We propose a unified exact approach for two different generalizations of the 0-1 Knapsack problem, that is the 0-1 Knapsack Problem with Setups and the 0-1 Collapsing Knapsack Problem. In the first problem, the items belong to disjoint families (or classes) and they can be picked only if the corresponding family is activated. The selection of a class involves setup costs and resource consumptions thus affecting both the objective function and the capacity constraint. In the 0-1 Collapsing Knapsack Problem the capacity of the knapsack is not a scalar but a non-increasing function of the number of items included, namely it is inversely related to the number of items placed inside the knapsack. The unified approach involves three main steps and relies on an effective exploration of a specific set of variables that leads to solve standard knapsack problems. It proves to be very effective both on the 0-1 Knapsack Problem with Setups and on the 0-1 Collapsing Knapsack Problem and is capable of solving to optimality large size instances with limited computational effort. The method significantly outperforms the state of art solver CPLEX 12.5 and compares favorably to the algorithms available in literature.