Palabras clave
tighter formulations
knapsack constraints
dominated inequalities
Cubrimientos maximales
formulaciones más fuertes
restricciones de tipo mochila
desigualdades dominadas
Cómo citar
Resumen
En este trabajo se presenta un procedimiento enumerativo que identifica todos los cubrimientos maximales respecto del conjunto de cubrimientos implicados por una restricción de tipo mochila con variables 0-1. Las desigualdades inducidas por estos cubrimientos maximales no están dominadas por la desigualdad inducida por ningún otro cubrimiento implicado por la restricción de tipo mochila. Así pues, su identificación puede contribuir al reforzamiento de formulaciones de problemas de programación 0-1. Por otra parte, se presenta una mejora de un procedimiento de la literatura existente que únicamente identifica ciertos cubrimientos maximales. Además, se muestran algunos resultados computacionales comparativos en los que ambos procedimientos se han aplicado a restricciones de tipo mochila generadas aleatoriamente.
Citas
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.