Familias de desigualdades válidas para el poliedro de packing de caterpillars

En este trabajo estudiamos el poliedro asociado con una formulación natural de 2-SSCPsc como un modelo de programación lineal entera. Estudiamos propiedades elementales de este poliedro, incluyendo un lema de lifting y las propiedades de facetitud de las restricciones del modelo. Una característic...

Descripción completa

Guardado en:
Detalles Bibliográficos
Autor principal: Marenco, Javier
Formato: Objeto de conferencia Resumen
Lenguaje:Español
Publicado: 2015
Materias:
Ciencias Informáticas
caterpillar
grafo
desigualdades
Acceso en línea:http://sedici.unlp.edu.ar/handle/10915/59184
http://44jaiio.sadio.org.ar/sites/default/files/sio1-1.pdf
Aporte de:
SEDICI (UNLP) de Universidad Nacional de La Plata
id I19-R120-10915-59184
record_format dspace
institution Universidad Nacional de La Plata
institution_str I-19
repository_str R-120
collection SEDICI (UNLP)
language Español
topic Ciencias Informáticas
caterpillar
grafo
desigualdades
spellingShingle Ciencias Informáticas
caterpillar
grafo
desigualdades
Marenco, Javier
Familias de desigualdades válidas para el poliedro de packing de caterpillars
topic_facet Ciencias Informáticas
caterpillar
grafo
desigualdades
description En este trabajo estudiamos el poliedro asociado con una formulación natural de 2-SSCPsc como un modelo de programación lineal entera. Estudiamos propiedades elementales de este poliedro, incluyendo un lema de lifting y las propiedades de facetitud de las restricciones del modelo. Una característica interesante de este poliedro es que muchas de las desigualdades válidas que definen facetas se pueden deducir a partir de desigualdades válidas más sencillas. Sobre la base de esta observación presentamos varios procedimientos para construir desigualdades válidas a partir de desigualdades más sencillas, y estudiamos condiciones que garantizan que las desigualdades obtenidas definen facetas. Estos resultados permiten hallar varias familias de facetas de este poliedro y proponer procedimientos constructivos para los problemas de separación asociados con estas familias.
format Objeto de conferencia
Resumen
author Marenco, Javier
author_facet Marenco, Javier
author_sort Marenco, Javier
title Familias de desigualdades válidas para el poliedro de packing de caterpillars
title_short Familias de desigualdades válidas para el poliedro de packing de caterpillars
title_full Familias de desigualdades válidas para el poliedro de packing de caterpillars
title_fullStr Familias de desigualdades válidas para el poliedro de packing de caterpillars
title_full_unstemmed Familias de desigualdades válidas para el poliedro de packing de caterpillars
title_sort familias de desigualdades válidas para el poliedro de packing de caterpillars
publishDate 2015
url http://sedici.unlp.edu.ar/handle/10915/59184
http://44jaiio.sadio.org.ar/sites/default/files/sio1-1.pdf
work_keys_str_mv AT marencojavier familiasdedesigualdadesvalidasparaelpoliedrodepackingdecaterpillars
bdutipo_str Repositorios
_version_ 1764820478214537216

Ejemplares similares