An enumerative procedure for identifying maximal covers

• Muñoz, Susana ^[1]
  1. [1] Universidad Complutense de Madrid

     Universidad Complutense de Madrid

     Madrid, España

     
• Localización: Revista de Matemática: Teoría y Aplicaciones, ISSN 2215-3373, ISSN-e 2215-3373, Vol. 10, Nº. 1-2, 2003, págs. 173-186
• Idioma: inglés
• DOI: 10.15517/rmta.v10i1-2.233
• Enlaces
  • Texto completo (pdf)
• Resumen
  • español

    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

  • English

    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

• 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...
  • 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”,...
  • Escudero, L.F.; Muñoz, S. (1998) “On characterizing tighter formulations for 0-1 programs”, European Journal of Operational Research 106(1):...
  • 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...
  • Johnson, E.L.; Nemhauser, G.L.; Savelsbergh, M.W.P. (2000) “Progress in linear programming-based algorithms for integer programming: An exposition”,...
  • Muñoz, S. (1995) “A correction of the justification of the Dietrich-Escudero- Garín -Pérez O(n) procedures for identifying maximal cliques...
  • 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...
  • Savelsbergh, M.W.P. (1994) “Preprocessing and probing techniques for mixed integer programming problems”, ORSA Journal on Computing 6(4):...