A+A-Acessibilidade
EnglishPortuguese
Buscar
24 Set
14:00 Defesa de Mestrado Integralmente a distância
Tema
Algoritmos Exatos para o Problema de Empacotamento Quadrático
Aluno
Vítor Gomes Chagas
Orientador / Docente
Flávio Keidi Miyazawa
Breve resumo
Problemas de empacotamento possuem uma vasta aplicabilidade no mundo real, sendo de grande importância prática nos setores de indústria e serviços, bem como de grande relevância teórica para o estudo de problemas de otimização combinatória mais complexos. Nas variantes quadráticas desses problemas, cada par de itens está associado a um valor de dissimilaridade, representando uma penalidade ou um benefício ao serem empacotados juntos. Essa característica adicional faz com que esses problemas generalizem diversas variantes do problema de empacotamento clássico e de particionamento em grafos, tornando-os de grande interesse teórico e prático. Nesta dissertação, estudamos o problema de empacotamento quadrático com itens unidimensionais sob a abordagem de algoritmos exatos. Propomos formulações baseadas em Programação Linear Inteira para o problema, que se dividem em formulações de tamanho polinomial estendidadas de soluções para o problema da k-partição em grafos, formulações de tamanho pseudopolinomial inspiradas em modelos de fluxo em arcos para o problema de empacotamento clássico, e uma formulação com uma quantidade exponencial de variáveis que é resolvida por meio de geração de colunas e um algoritmo Branch-and-Price. Também investigamos algumas rotinas de pré-processamento que objetivam reduzir instâncias antes de serem resolvidas de forma exata. Concluímos o trabalho com um estudo comparativo dessas soluções por meio de experimentos computacionais em instâncias adaptadas da literatura, e a discussão dos resultados obtidos.
Banca examinadora
Titulares:
Flávio Keidi Miyazawa IC/UNICAMP
Manoel Bezerra Campêlo Neto DEMA/UFC
Ricardo Fukasawa UWATERLOO
Suplentes:
Eduardo Candido Xavier IC/UNICAMP
Kelly Cristina Poldi IMECC/UNICAMP