A new exact approach for the 0-1 Collapsing Knapsack Problem

We consider the 0/1 Collapsing Knapsack Problem (CKP) and a generalization involving more than a capacity constraint (M-CKP). We propose a novel ILP formulation and a problem reduction procedure together with an exact approach. The proposed approach compares favorably to the methods available in the literature and manages to solve to optimality very large size instances particularly for CKP and 2-CKP.