Detecting constraint redundancy in 0-1 linear programming problems

Detecting constraint redundancy in 0-1 linear programming problems

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 prog...

Descripción completa

Detalles Bibliográficos
Autor principal: Muñoz, Susana
Formato: Online
Idioma:spa
Publicado: Universidad de Costa Rica, Centro de Investigación en Matemática Pura y Aplicada (CIMPA) 2001
Acceso en línea:https://revistas.ucr.ac.cr/index.php/matematica/article/view/193
id RMTA193
record_format ojs
spelling RMTA1932022-01-17T18:21:23Z Detecting constraint redundancy in 0-1 linear programming problems Detecting constraint redundancy in 0-1 linear programming problems Muñoz, Susana Redundant constraints packings coverings special ordered sets admissible families Restricciones redundantes empaquetamientos recubrimientos conjuntos ordenados especiales familias admisibles 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.   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. Universidad de Costa Rica, Centro de Investigación en Matemática Pura y Aplicada (CIMPA) 2001-02-01 info:eu-repo/semantics/article info:eu-repo/semantics/publishedVersion Article application/pdf https://revistas.ucr.ac.cr/index.php/matematica/article/view/193 10.15517/rmta.v8i1.193 Revista de Matemática: Teoría y Aplicaciones; Vol. 8 No. 1 (2001): Revista de Matemática: Teoría y Aplicaciones; 1-12 Revista de Matemática: Teoría y Aplicaciones; Vol. 8 Núm. 1 (2001): Revista de Matemática: Teoría y Aplicaciones; 1-12 Revista de Matemática; Vol. 8 N.º 1 (2001): Revista de Matemática: Teoría y Aplicaciones; 1-12 2215-3373 1409-2433 spa https://revistas.ucr.ac.cr/index.php/matematica/article/view/193/173 Derechos de autor 2001 Revista de Matemática: Teoría y Aplicaciones
institution Universidad de Costa Rica
collection Revista de Matemática: Teoría y Aplicaciones
language spa
format Online
author Muñoz, Susana
spellingShingle Muñoz, Susana
Detecting constraint redundancy in 0-1 linear programming problems
author_facet Muñoz, Susana
author_sort Muñoz, Susana
description 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.
title Detecting constraint redundancy in 0-1 linear programming problems
title_short Detecting constraint redundancy in 0-1 linear programming problems
title_full Detecting constraint redundancy in 0-1 linear programming problems
title_fullStr Detecting constraint redundancy in 0-1 linear programming problems
title_full_unstemmed Detecting constraint redundancy in 0-1 linear programming problems
title_sort detecting constraint redundancy in 0-1 linear programming problems
title_alt Detecting constraint redundancy in 0-1 linear programming problems
publisher Universidad de Costa Rica, Centro de Investigación en Matemática Pura y Aplicada (CIMPA)
publishDate 2001
url https://revistas.ucr.ac.cr/index.php/matematica/article/view/193
work_keys_str_mv AT munozsusana detectingconstraintredundancyin01linearprogrammingproblems
_version_ 1811744058817642496

Ejemplares similares