Universidad de Costa Rica
  • Sobre Kérwá
  • Acceso Abierto
  • Cómo Depositar
  • Políticas
  • Contacto
    • español
    • English
  • English 
    • español
    • English
  • Login
View Item 
  •   Kérwá Home
  • Publicaciones periódicas de la Universidad de Costa Rica
  • Revista de Matemática: Teoría y Aplicaciones
  • Revista de Matemáticas 10(1 y 2)
  • View Item
  •   Kérwá Home
  • Publicaciones periódicas de la Universidad de Costa Rica
  • Revista de Matemática: Teoría y Aplicaciones
  • Revista de Matemáticas 10(1 y 2)
  • View Item
JavaScript is disabled for your browser. Some features of this site may not work without it.

An enumerative procedure for identifying maximal covers

An enumerative procedure for identifying maximal covers

artículo científico
Thumbnail
View/Open
233-444-1-PB.pdf (320.9Kb)
Date
2009-02-20
Author
Muñoz, Susana
Metadata
Show full item record
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
 
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
 
URI
https://hdl.handle.net/10669/12876
External link to the item
10.15517/rmta.v10i1-2.233
http://revistas.ucr.ac.cr/index.php/matematica/article/view/233
Collections
  • Revista de Matemáticas 10(1 y 2) [14]



  • Repositorios universitarios

  • Repositorio del SIBDI-UCR
  • Biblioteca Digital del CIICLA
  • Repositorio Documental Rafael Obregón Loría (CIHAC)
  • Biblioteca Digital Carlos Melendez (CIHAC)
  • Repositorio de Fotografías
  • Colección de videos de UPA-VAS
  • Sitios recomendados

  • Buscador regional de LA Referencia
  • Buscador del Open ROAR
  • Scientific Electronic Library Online (SciELO)
  • Directory of Open Access Journals (DOAJ)
  • Redalyc
  • Redes sociales

  • facebook.com/repositoriokerwa
  • @Ciencia_UCR
  • Sobre Kérwá
  • Acceso Abierto
  • Cómo depositar
  • Políticas
Contact Us | Send Feedback
Repositorio Institucional de la Universidad de Costa Rica. Algunos derechos reservados. Este repositorio funciona con DSpace.
 

 

Browse

All of KérwáCommunities & CollectionsTitlesAuthorsSubjectsProcedenceTypeThis CollectionTitlesAuthorsSubjectsProcedenceType

My Account

LoginRegister

  • Repositorios universitarios

  • Repositorio del SIBDI-UCR
  • Biblioteca Digital del CIICLA
  • Repositorio Documental Rafael Obregón Loría (CIHAC)
  • Biblioteca Digital Carlos Melendez (CIHAC)
  • Repositorio de Fotografías
  • Colección de videos de UPA-VAS
  • Sitios recomendados

  • Buscador regional de LA Referencia
  • Buscador del Open ROAR
  • Scientific Electronic Library Online (SciELO)
  • Directory of Open Access Journals (DOAJ)
  • Redalyc
  • Redes sociales

  • facebook.com/repositoriokerwa
  • @Ciencia_UCR
  • Sobre Kérwá
  • Acceso Abierto
  • Cómo depositar
  • Políticas
Contact Us | Send Feedback
Repositorio Institucional de la Universidad de Costa Rica. Algunos derechos reservados. Este repositorio funciona con DSpace.