Detecting constraint redundancy in 0-1 linear programming problems

• 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. 8, Nº. 1, 2001, págs. 1-12
• Idioma: inglés
• DOI: 10.15517/rmta.v8i1.193
• Enlaces
  • Texto completo (pdf)
• Resumen
  • español

    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.Palabras Clave: Restricciones redundantes, empaquetamientos, recubrimientos, conjuntos ordenados especiales, familias admisibles.

  • English

    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.Keywords: Redundant constraints, packings, coverings, special ordered sets, admissible families

• Referencias bibliográficas
  • Atamtürk, A.; Nemhauser, G.L.; Savelsbergh, M.W.P. (2000) “Conflict graphs in solving integer programming problems”, European Journal of...
  • Bixby, R.E.; Ceria, S.; McZeal, C.M.; Savelsbergh, M.W.P. (1998) “An updated mixed integer programming library: MIPLIB 3.0”, Technical Report...
  • 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...
  • Escudero, L.F.; Garín, A.; Pérez, G. (1996) “On using clique overlapping for detecting knapsack constraint redundancy and infeasibility in...
  • Escudero, L.F.; Muñoz, S. (1998) “On characterizing tighter formulations for 0-1 programs”, European Journal of Operational Research 106(1):...
  • Guignard, M.; Spielberg, K. (1981) “Logical reduction methods in zero-one programming. Minimal preferred variables”, Operations Research 29(1):...
  • 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.; Kostreva, M.M.; Suhl, U.H. (1985) “Solving 0-1 integer programming problems arising from large scale planning models”, Operations...
  • 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. (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):...