Palabras clave
packings
coverings
special ordered sets
admissible families
Restricciones redundantes
empaquetamientos
recubrimientos
conjuntos ordenados especiales
familias admisibles
Cómo citar
Resumen
En este trabajo se presenta un procedimiento de obtención de cotas superiores para una función lineal a partir de ciertas familias de empaquetamientos, cubrimientos y conjuntos ordenados especiales. Asimismo, s e presenta un nuevo método de detección de restricciones redundantes en problemas de programación lineal 0-1 basado en dichas cotas que permite considerar conjuntamente varias restricciones. Además, se muestra una situación de redundancia que es detectada por este método, pero no por los métodos tradicionales, los cuales consideran las restricciones individualmente.
Citas
Atamtürk, A.; Nemhauser, G.L.; Savelsbergh, M.W.P. (2000) “Conflict graphs in solving integer programming problems”, European Journal of Operational Research 121(1): 40–55.
Bixby, R.E.; Ceria, S.; McZeal, C.M.; Savelsbergh, M.W.P. (1998) “An updated mixed integer programming library: MIPLIB 3.0”, Technical Report TR98-03, Department of Computational and Applied Mathematics, Rice University. Available from URL: http://www.caam.rice.edu/˜bixby/miplib/miplib.html
Crowder, H.; Johnson, E.L.; Padberg, M. (1983) “Solving large-scale zero-one linear programming problems”, Operations Research 31(5): 803–834.
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.; Garín, A.; Pérez, G. (1996) “On using clique overlapping for detecting knapsack constraint redundancy and infeasibility in 0-1 mixed integer programs”, Top 4(1): 87–98.
Escudero, L.F.; Muñoz, S. (1998) “On characterizing tighter formulations for 0-1 programs”, European Journal of Operational Research 106(1): 172–176.
Guignard, M.; Spielberg, K. (1981) “Logical reduction methods in zero-one programming. Minimal preferred variables”, Operations Research 29(1): 49–74.
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.; Kostreva, M.M.; Suhl, U.H. (1985) “Solving 0-1 integer programming problems arising from large scale planning models”, Operations Research 33(4): 803–819.
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. (1988) Integer and Combinatorial Optimization. John Wiley, New York.
Savelsbergh, M.W.P. (1994) “Preprocessing and probing techniques for mixed integer programming problems”, ORSA Journal on Computing 6(4): 445–454.