An enumerative procedure for identifying maximal covers
- 1 Universidad Complutense de Madrid, Departamento de Estadística e Investigación Operativa I, Facultad de Ciencias Matemáticas
ISSN: 2215-3373, 2215-3373
Year of publication: 2003
Volume: 10
Issue: 1-2
Pages: 173-186
Type: Article
More publications in: Revista de Matemática: Teoría y Aplicaciones
Abstract
In this paper we present an enumerative procedure for identifying all maximalcovers from the set of covers implied by a 0-1 knapsack constraint. The inequalitiesinduced by these maximal covers are not dominated by the inequality induced by anyother cover implied by the knapsack constraint. Thus, their identification can help totighten 0-1 models. On the other hand, we present an improvement on a proceduretaken from the literature for identifying certain maximal covers. Some comparativecomputational experiments where both procedures have been applied to randomlygenerated knapsack constraints are also reported.Keywords: Maximal covers, tighter formulations, knapsack constraints, dominated inequalities
Bibliographic References
- Dietrich, B.L.; Escudero, L.F.; Garín, A.; Pérez, G. (1993) “O(n) procedures for identifying maximal cliques and non-dominated extensions of consecutive minimal covers and alternates”, Top 1(1): 139–160.
- Escudero, L.F.; Martello, S.; Toth, P. (1998) “On tightening 0-1 programs based on extensions of pure 0-1 knapsack and subset-sum problems”, Annals of Operations Research 81: 379–404.
- Escudero, L.F.; Muñoz, S. (1998) “On characterizing tighter formulations for 0-1 programs”, European Journal of Operational Research 106(1): 172–176.
- Escudero, L.F.; Muñoz, S. (2002) “On characterizing maximal covers”, Investigación Operacional (to appear).
- Hoffman, K.L.; Padberg, M. (1991) “Improving LP-representations of zero-one linear programs for branch-and-cut”, ORSA Journal on Computing 3(2): 121–134.
- Johnson, E.L.; Nemhauser, G.L.; Savelsbergh, M.W.P. (2000) “Progress in linear programming-based algorithms for integer programming: An exposition”, INFORMS Journal on Computing 12(1): 2–23.
- Muñoz, S. (1995) “A correction of the justification of the Dietrich-Escudero- Garín -Pérez O(n) procedures for identifying maximal cliques and non-dominated extensions of consecutive minimal covers and alternates”, Top 3(1): 161–165.
- Muñoz, S. (1999) Reforzamiento de Modelos en Programación Lineal 0-1. Tesis Doctoral, Universidad Complutense de Madrid, Madrid.
- Nemhauser, G.L.; Wolsey, L.A. (1998) Integer and Combinatorial Optimization. John Wiley, New York.
- Press, W.H.; Teukolsky, S.A.; Vetterling, W.T.; Flannery, B.P. (1992) Numerical Recipes in FORTRAN. The Art of Scientific Computing. Cambridge University Press.
- Savelsbergh, M.W.P. (1994) “Preprocessing and probing techniques for mixed integer programming problems”, ORSA Journal on Computing 6(4): 445–454.