Mostrar el registro sencillo del ítem
An enumerative procedure for identifying maximal covers
An enumerative procedure for identifying maximal covers
dc.creator | Muñoz, Susana | |
dc.date.accessioned | 2015-05-19T18:35:22Z | |
dc.date.available | 2015-05-19T18:35:22Z | |
dc.date.issued | 2009-02-20 00:00:00 | |
dc.identifier.citation | http://revistas.ucr.ac.cr/index.php/matematica/article/view/233 | |
dc.identifier.issn | ||
dc.identifier.uri | https://hdl.handle.net/10669/12876 | |
dc.description.abstract | In this paper we present an enumerative procedure for identifying all maximalcovers from the set of covers implied by a 0-1 knapsack constraint. The inequalitiesinduced by these maximal covers are not dominated by the inequality induced by anyother cover implied by the knapsack constraint. Thus, their identification can help totighten 0-1 models. On the other hand, we present an improvement on a proceduretaken from the literature for identifying certain maximal covers. Some comparativecomputational experiments where both procedures have been applied to randomlygenerated knapsack constraints are also reported.Keywords: Maximal covers, tighter formulations, knapsack constraints, dominated inequalities | |
dc.description.abstract | En este trabajo se presenta un procedimiento enumerativo que identifica todos loscubrimientos maximales respecto del conjunto de cubrimientos implicados por unarestricci´on de tipo mochila con variables 0-1. Las desigualdades inducidas por estoscubrimientos maximales no est´an dominadas por la desigualdad inducida por ning´unotro cubrimiento implicado por la restricci´on de tipo mochila. As´? pues, su identificaci´on puede contribuir al reforzamiento de formulaciones de problemas de programaci´on 0-1. Por otra parte, se presenta una mejora de un procedimiento de la literaturaexistente que ´unicamente identifica ciertos cubrimientos maximales. Adem´as,se muestran algunos resultados computacionales comparativos en los que ambos procedimientosse han aplicado a restricciones de tipo mochila generadas aleatoriamente.Palabras clave: Cubrimientos maximales, formulaciones m´as fuertes, restricciones detipo mochila, desigualdades dominadas | |
dc.format.extent | 173-186 | |
dc.relation.ispartof | Revista de Matemática: Teoría y Aplicaciones Vol. 10 Núm. 1-2 2009 | |
dc.title | An enumerative procedure for identifying maximal covers | |
dc.title | An enumerative procedure for identifying maximal covers | |
dc.type | artículo original | |
dc.date.updated | 2015-05-19T18:35:22Z | |
dc.language.rfc3066 | es | |
dc.identifier.doi | 10.15517/rmta.v10i1-2.233 |