ON CHARACTERIZING MAXIMAL COVERS

Abstract

In this paper we introduce the concept of maximal covers and provide some characterizations that make the identification of the maximal covers from the set of covers implied by a 0-1 knapsack constraint easier. By construction, these maximal covers induce non-dominated valid inequalities for the set of feasible solutions for the Knapsack constraint. So, their identification can help to tightening 0-1 models. We also show some situations where a procedure taken from the literature for identifying non-dominated inequalities from certain types of covers only obtains a small subset of maximal covers