An exact approach for the 0–1 knapsack problem with setups

We consider the 0-1 Knapsack Problem with Setups. We propose an exact approach which handles the structure of the ILP formulation of the problem. It relies on partitioning the variables set into two levels and exploiting this partitioning. The proposed approach favorably compares to the algorithms in literature and to solver CPLEX 12.5 applied to the ILP formulation. It turns out to be very effective and capable of solving to optimality, within limited CPU time, all instances with up to 100,000 variables.