Detecting constraint redundancy in 0-1 linear programming problems

  1. Muñoz, Susana 1
  1. 1 Universidad Complutense de Madrid, Departamento de Estadística e Investigación Operativa I, Facultad de Ciencias Matemáticas
Journal:
Revista de Matemática: Teoría y Aplicaciones

ISSN: 2215-3373,  2215-3373

Year of publication: 2001

Volume: 8

Issue: 1

Pages: 1-12

Type: Article

DOI: 10.15517/RMTA.V8I1.193 DIALNET GOOGLE SCHOLAR lock_openDialnet editor

More publications in: Revista de Matemática: Teoría y Aplicaciones

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

Bibliographic 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.
Data source: Dialnet