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 Zeng and Richard [32]. For problems with a single cardinality constraint, we derive a set of multidimensional superadditive lifting functions and prove that they are maximal and non-dominated 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.
Article
View Sequence independent lifting for 0-1 knapsack problems with disjoint cardinality constraints