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...
Guardado en:
| Autor principal: | |
|---|---|
| Formato: | Objeto de conferencia Resumen |
| Lenguaje: | Español |
| Publicado: |
2015
|
| Materias: | |
| 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: |
| Sumario: | 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. |
|---|