Detecting constraint redundancy in 0-1 linear programming problems
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 con...
| Main Author: | |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
Universidad de Costa Rica
2009-02-01
|
| Series: | Revista de Matemática: Teoría y Aplicaciones |
| Online Access: | https://revistas.ucr.ac.cr/index.php/matematica/article/view/193 |
| _version_ | 1797709269160689664 |
|---|---|
| author | Susana Muñoz |
| author_facet | Susana Muñoz |
| author_sort | Susana Muñoz |
| collection | DOAJ |
| description | 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 |
| first_indexed | 2024-03-12T06:34:06Z |
| format | Article |
| id | doaj.art-5bf61dd204ec4f7a83aa85ba68e6e75a |
| institution | Directory Open Access Journal |
| issn | 2215-3373 |
| language | English |
| last_indexed | 2024-03-12T06:34:06Z |
| publishDate | 2009-02-01 |
| publisher | Universidad de Costa Rica |
| record_format | Article |
| series | Revista de Matemática: Teoría y Aplicaciones |
| spelling | doaj.art-5bf61dd204ec4f7a83aa85ba68e6e75a2023-09-03T01:25:04ZengUniversidad de Costa RicaRevista de Matemática: Teoría y Aplicaciones2215-33732009-02-018111210.15517/rmta.v8i1.193178Detecting constraint redundancy in 0-1 linear programming problemsSusana Muñoz0Universidad Complutense de Madrid, Departamento de Estadística e Investigación Operativa I, Facultad de Ciencias MatemáticasIn 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 familieshttps://revistas.ucr.ac.cr/index.php/matematica/article/view/193 |
| spellingShingle | Susana Muñoz Detecting constraint redundancy in 0-1 linear programming problems Revista de Matemática: Teoría y Aplicaciones |
| title | 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_short | Detecting constraint redundancy in 0-1 linear programming problems |
| title_sort | detecting constraint redundancy in 0 1 linear programming problems |
| url | https://revistas.ucr.ac.cr/index.php/matematica/article/view/193 |
| work_keys_str_mv | AT susanamunoz detectingconstraintredundancyin01linearprogrammingproblems |