24set2021
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
Instituto de Computação
Privacy Overview

This website uses cookies so that we can provide you with the best user experience possible. Cookie information is stored in your browser and performs functions such as recognising you when you return to our website and helping our team to understand which sections of the website you find most interesting and useful.