Problema de empaquetamiento con conflictos generalizados

Mostrar todas las versiones(3)

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 m...

Descripción completa

Detalles Bibliográficos
Autor principal:	Pousa, Federico
Otros Autores:	Méndez-Díaz, Isabel
Formato:	Tesis doctoral publishedVersion
Lenguaje:	Español
Publicado:	Universidad de Buenos Aires. Facultad de Ciencias Exactas y Naturales 2018
Materias:	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
Acceso en línea:	https://hdl.handle.net/20.500.12110/tesis_n6364_Pousa https://repositoriouba.sisbi.uba.ar/gsdl/cgi-bin/library.cgi?a=d&c=aextesis&d=tesis_n6364_Pousa_oai
Aporte de:	Repositorio Digital de la Universidad de Buenos Aires (UBA) de Universidad de Buenos Aires

id	I28-R145-tesis_n6364_Pousa_oai
record_format	dspace
institution	Universidad de Buenos Aires
institution_str	I-28
repository_str	R-145
collection	Repositorio Digital de la Universidad de Buenos Aires (UBA)
language	Español
orig_language_str_mv	spa
topic	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
spellingShingle	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 Pousa, Federico Problema de empaquetamiento con conflictos generalizados
topic_facet	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
description	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.
author2	Méndez-Díaz, Isabel
author_facet	Méndez-Díaz, Isabel Pousa, Federico
format	Tesis doctoral Tesis doctoral publishedVersion
author	Pousa, Federico
author_sort	Pousa, Federico
title	Problema de empaquetamiento con conflictos generalizados
title_short	Problema de empaquetamiento con conflictos generalizados
title_full	Problema de empaquetamiento con conflictos generalizados
title_fullStr	Problema de empaquetamiento con conflictos generalizados
title_full_unstemmed	Problema de empaquetamiento con conflictos generalizados
title_sort	problema de empaquetamiento con conflictos generalizados
publisher	Universidad de Buenos Aires. Facultad de Ciencias Exactas y Naturales
publishDate	2018
url	https://hdl.handle.net/20.500.12110/tesis_n6364_Pousa https://repositoriouba.sisbi.uba.ar/gsdl/cgi-bin/library.cgi?a=d&c=aextesis&d=tesis_n6364_Pousa_oai
work_keys_str_mv	AT pousafederico problemadeempaquetamientoconconflictosgeneralizados AT pousafederico binpackingproblemwithgeneralizedconflicts
_version_	1824356183649026048
spelling	I28-R145-tesis_n6364_Pousa_oai2024-09-02 Méndez-Díaz, Isabel Zabala, Paula Pousa, Federico 2018-03-26 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. The Bin Packing Problem with Generalized Conflicts (BPGC) is a generalization of the Bin Packing Problem in which the items to be assigned present conflict among subsets of them. This problem arises naturally in situations when an assignment problem has to be solved minimizingthe number of containers used, but with the addition that the items can not be assigned to a container without checking that the assignation is compliant with the conflicts between the items. In the literature of Bin Packing Problems, there is no computational treatment for this problem with an Integer Programming approach. However, there is a particular case of this problem, the one where the items only have conflicts among pairs of them, that has some papers devoted to it. In this thesis the problem mentioned above is treated by proposing formulations based on Integer Linear Programming. For the formulations used, a theoretical study is presented consisting of the minimal system of the polyhedron along with several families of valid inequalities. Then, inthe case of many families, proofs are given showing the special conditions that they need to fulfil in order to be facet defining for the polyhedron. Then, from the practical point of view, a branch-and-cut algorithm was developed designing several components. Firstly, many heuristics and metaheuristics were developed in order to get primal solutions of good quality. Then, the strongest families of valid inequalities were addedto the algorithm, besides many more specific components, willing to get a robust and efficient algorithm. As a final step, the algorithm was tested against a vast set of instances to analyze its efficiency. Very good quality results were obtained showing the feasibility of the usage of thisapproach in real life situations. Fil: Pousa, Federico. Universidad de Buenos Aires. Facultad de Ciencias Exactas y Naturales; Argentina. application/pdf https://hdl.handle.net/20.500.12110/tesis_n6364_Pousa spa Universidad de Buenos Aires. Facultad de Ciencias Exactas y Naturales info:eu-repo/semantics/openAccess https://creativecommons.org/licenses/by-nc-sa/2.5/ar 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 Problema de empaquetamiento con conflictos generalizados Bin packing problem with generalized conflicts info:eu-repo/semantics/doctoralThesis info:ar-repo/semantics/tesis doctoral info:eu-repo/semantics/publishedVersion https://repositoriouba.sisbi.uba.ar/gsdl/cgi-bin/library.cgi?a=d&c=aextesis&d=tesis_n6364_Pousa_oai

Problema de empaquetamiento con conflictos generalizados

Ejemplares similares