Sequence Independent Lifting for 0-1 Knapsack Problems With Disjoint Cardinality Constraints

In this paper, we study the set of 0-1 integer solutions to a single knapsack constraint and a set of non-overlapping cardinality constraints (MCKP). This set is a generalization of the traditional 0-1 knapsack polytope and the 0-1 knapsack polytope with generalized upper bounds. We derive strong valid inequalities for the convex hull of its feasible solutions by lifting the generalized cover inequalities presented in [32]. For problems with a single cardinality constraint, we derive a set of multidimensional superadditive lifting functions and prove that they are maximal and nondominated under some mild conditions. We then show that these functions can also be used to build strong valid inequalities for problems with multiple disjoint cardinality constraints