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
Año de publicación: 2003
Volumen: 10
Número: 1-2
Páginas: 173-186
Tipo: Artículo
Otras publicaciones en: Revista de Matemática: Teoría y Aplicaciones
Resumen
En este trabajo se presenta un procedimiento enumerativo que identifica todos loscubrimientos maximales respecto del conjunto de cubrimientos implicados por unarestricci´on de tipo mochila con variables 0-1. Las desigualdades inducidas por estoscubrimientos maximales no est´an dominadas por la desigualdad inducida por ning´unotro cubrimiento implicado por la restricci´on de tipo mochila. As´? pues, su identificaci´on puede contribuir al reforzamiento de formulaciones de problemas de programaci´on 0-1. Por otra parte, se presenta una mejora de un procedimiento de la literaturaexistente que ´unicamente identifica ciertos cubrimientos maximales. Adem´as,se muestran algunos resultados computacionales comparativos en los que ambos procedimientosse han aplicado a restricciones de tipo mochila generadas aleatoriamente.Palabras clave: Cubrimientos maximales, formulaciones m´as fuertes, restricciones detipo mochila, desigualdades dominadas
Referencias bibliográficas
- 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.