On characterizing maximal covers

On characterizing maximal covers

0.00 Avg rating0 Votes
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: ,
Keywords: knapsack problem
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 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.

Reviews

Required fields are marked *. Your email address will not be published.