24 set 2021
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 |