Article ID: | iaor20031217 |
Country: | Cuba |
Volume: | 23 |
Issue: | 2 |
Start Page Number: | 136 |
End Page Number: | 149 |
Publication Date: | May 2002 |
Journal: | Revista de Investigacin Operacional |
Authors: | Escudero L.F., Muoz S. |
Keywords: | knapsack problem |
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 in 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.