Problema de empaquetamiento con conflictos generalizados

Institución otorgante:

Universidad de Buenos Aires. Facultad de Ciencias Exactas y Naturales

Fecha:

2018-03-26

Tipo de documento: 

info:eu-repo/semantics/doctoralThesis
 

Formato:

application/pdf

Idioma:

spa

Temas:

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

Descripción:

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 deasignació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 devarias 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 algoritmomá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.

Identificador:

https://hdl.handle.net/20.500.12110/tesis_n6364_Pousa