Keywords
packings
coverings
special ordered sets
admissible families
Restricciones redundantes
empaquetamientos
recubrimientos
conjuntos ordenados especiales
familias admisibles
How to Cite
Abstract
In this paper we present a procedure for obtaining upper bounds on a linear function by means of certain families of packings, coverings and special ordered sets. We also present a new method for detecting redundant constraints in 0-1 linear programming problems based on these bounds that allows consideration of several constraints jointly. Furthermore, we show a redundancy situation which is detected by this new method, but not by the traditional methods, which consider the constraints individually.
References
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.