Catálogo de publicaciones - tesis
Título de Acceso Abierto
Problema de empaquetamiento con conflictos generalizados
Federico Pousa Isabel Méndez-Díaz Paula Zabala
publishedVersion.
Resumen/Descripción – provisto por el repositorio digital
El problema de empaquetamiento con confictos generalizados (PECG) es una generalización del problema de empaquetamiento en el cual los ítems a asignar presentan conflictos entre subconjuntos de ellos. Este problema surge naturalmente en situaciones donde se quiere resolver un problema de asignación minimizando la cantidad de contenedores utilizados, pero en donde los ítems no pueden ser asignados de forma irrestricta, sino que la asignación depende de los conflictos que se presentan entre ellos. En la literatura del área, no existe un tratamiento computacional para este problema, aunque sí se considera el caso particular en donde los ítems presentan conflictos de a pares. En esta tesis se aborda el PECG mediante la formulación de modelos de Programación Lineal Entera. Para el modelo propuesto, se presenta un estudio teórico que consta de derivar el sistema minimal del poliedro asociado y familias de desigualdades válidas. Luego, en el caso de varias familias, se demuestra bajo que condiciones definen facetas del poliedro en cuestión. Simultaneamente, desde el aspecto práctico, se desarrolló un algoritmo branch-and-cut que incorpora diferentes componentes. En primer lugar se desarrollaron varias heurísticas y metaheurísticas para conseguir buenas soluciones primales. Luego, se incorporaron las familias de desigualdades más fuertes como planos de corte, junto con otras componentes particulares, para conseguir un algoritmo más robusto y eficiente. Por último, se experimentó con un extenso conjunto de instancias para analizar el desempeño, obteniendo muy buenos resultados que muestran la factibilidad de la utilización del enfoque en la práctica.Palabras clave – provistas por el repositorio digital
PROBLEMA DE EMPAQUETAMIENTO; OPTIMIZACION COMBINATORIA; PROGRAMACION LINEAL ENTERA; ALGORITMO BRANCH AND CUT; ESTUDIO POLIEDRAL; GRAFO DE CONFLICTOS; ASIGNACION EN HIPERGRAFOS; BIN PACKING PROBLEMS; COMBINATORIAL OPTIMIZATION; INTEGER PROGRAMMING; BRANCH AND CUT ALGORITHM; POLYHEDRAL STUDY; CONFLICTS GRAPH; ASSIGNATION IN HYPERGRAPH
Disponibilidad
| Institución detectada | Año de publicación | Navegá | Descargá | Solicitá |
|---|---|---|---|---|
| No requiere | 2018 | Biblioteca Digital (FCEN-UBA) (SNRD) |
|
Información
Tipo de recurso:
tesis
Idiomas de la publicación
- español castellano
País de edición
Argentina
Fecha de publicación
2018-03-26
Información sobre licencias CC
