We investigate the 0-1 knapsack problem with additional set packing constraints. First, we introduce a family of facet-defining clique inequalities. Then, we focus on lifted cover inequalities and we define upper and lower bounds on the lifting coefficients. We also introduce a family of lifted cover inequalities where some of the lifting coefficients are set to their upper bound, and the remaining ones are set at their lower bound. Finally, we specialize our results to the knapsack problem with generalized upper bound constraints, where the set packing constraints must be non-overlapping.
['Roberto J. Cañavate', 'Mercedes Landete']
A polyhedral study on 0-1 knapsack problems with set packing constraints