An enumerative procedure for identifying maximal covers

An enumerative procedure for identifying maximal covers

En este trabajo se presenta un procedimiento enumerativo que identifica todos los cubrimientos maximales respecto del conjunto de cubrimientos implicados por una restricción de tipo mochila con variables 0-1. Las desigualdades inducidas por estos cubrimientos maximales no están dominadas por la desi...

Descripción completa

Detalles Bibliográficos
Autor principal: Muñoz, S.
Formato: Online
Idioma:spa
Publicado: Universidad de Costa Rica, Centro de Investigación en Matemática Pura y Aplicada (CIMPA) 2003
Acceso en línea:https://revistas.ucr.ac.cr/index.php/matematica/article/view/233
id RMTA233
record_format ojs
spelling RMTA2332022-01-19T16:07:14Z An enumerative procedure for identifying maximal covers An enumerative procedure for identifying maximal covers Muñoz, S. Maximal covers tighter formulations knapsack constraints dominated inequalities Cubrimientos maximales formulaciones más fuertes restricciones de tipo mochila desigualdades dominadas In this paper we present an enumerative procedure for identifying all maximal covers from the set of covers implied by a 0-1 knapsack constraint. The inequalities induced by these maximal covers are not dominated by the inequality induced by any other cover implied by the knapsack constraint. Thus, their identification can help to tighten 0-1 models. On the other hand, we present an improvement on a procedure taken from the literature for identifying certain maximal covers. Some comparative computational experiments where both procedures have been applied to randomly generated knapsack constraints are also reported. En este trabajo se presenta un procedimiento enumerativo que identifica todos los cubrimientos maximales respecto del conjunto de cubrimientos implicados por una restricción de tipo mochila con variables 0-1. Las desigualdades inducidas por estos cubrimientos maximales no están dominadas por la desigualdad inducida por ningún otro cubrimiento implicado por la restricción de tipo mochila. Así pues, su identificación puede contribuir al reforzamiento de formulaciones de problemas de programación 0-1. Por otra parte, se presenta una mejora de un procedimiento de la literatura existente que únicamente identifica ciertos cubrimientos maximales. Además, se muestran algunos resultados computacionales comparativos en los que ambos procedimientos se han aplicado a restricciones de tipo mochila generadas aleatoriamente. Universidad de Costa Rica, Centro de Investigación en Matemática Pura y Aplicada (CIMPA) 2003-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/233 10.15517/rmta.v10i1-2.233 Revista de Matemática: Teoría y Aplicaciones; Vol. 10 No. 1-2 (2003): Revista de Matemática: Teoría y Aplicaciones; 173-186 Revista de Matemática: Teoría y Aplicaciones; Vol. 10 Núm. 1-2 (2003): Revista de Matemática: Teoría y Aplicaciones; 173-186 Revista de Matemática; Vol. 10 N.º 1-2 (2003): Revista de Matemática: Teoría y Aplicaciones; 173-186 2215-3373 1409-2433 spa https://revistas.ucr.ac.cr/index.php/matematica/article/view/233/213 Derechos de autor 2003 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, S.
spellingShingle Muñoz, S.
An enumerative procedure for identifying maximal covers
author_facet Muñoz, S.
author_sort Muñoz, S.
description En este trabajo se presenta un procedimiento enumerativo que identifica todos los cubrimientos maximales respecto del conjunto de cubrimientos implicados por una restricción de tipo mochila con variables 0-1. Las desigualdades inducidas por estos cubrimientos maximales no están dominadas por la desigualdad inducida por ningún otro cubrimiento implicado por la restricción de tipo mochila. Así pues, su identificación puede contribuir al reforzamiento de formulaciones de problemas de programación 0-1. Por otra parte, se presenta una mejora de un procedimiento de la literatura existente que únicamente identifica ciertos cubrimientos maximales. Además, se muestran algunos resultados computacionales comparativos en los que ambos procedimientos se han aplicado a restricciones de tipo mochila generadas aleatoriamente.
title An enumerative procedure for identifying maximal covers
title_short An enumerative procedure for identifying maximal covers
title_full An enumerative procedure for identifying maximal covers
title_fullStr An enumerative procedure for identifying maximal covers
title_full_unstemmed An enumerative procedure for identifying maximal covers
title_sort enumerative procedure for identifying maximal covers
title_alt An enumerative procedure for identifying maximal covers
publisher Universidad de Costa Rica, Centro de Investigación en Matemática Pura y Aplicada (CIMPA)
publishDate 2003
url https://revistas.ucr.ac.cr/index.php/matematica/article/view/233
work_keys_str_mv AT munozs anenumerativeprocedureforidentifyingmaximalcovers
AT munozs enumerativeprocedureforidentifyingmaximalcovers
_version_ 1811744064974880768

Ejemplares similares