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
Revista:
Revista de Matemática: Teoría y Aplicaciones

ISSN: 2215-3373,  2215-3373

Año de publicación: 2001

Volumen: 8

Número: 1

Páginas: 1-12

Tipo: Artículo

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

Otras publicaciones en: Revista de Matemática: Teoría y Aplicaciones

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

Referencias bibliográficas

  • 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.
Fuente de los datos: Dialnet